perm filename V2F.IN[1,DEK] blob
sn#285509 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 223 galley 1E
C00022 00003 folio 229 galley 2E NOTE:Middle and end of this galley couldn't be read.
C00034 00004 folio 234 galley 1
C00051 00005 folio 237 galley 2
C00070 00006 folio 241 galley 3
C00091 00007 folio 245 galley 4
C00107 00008 folio 249 galley 5
C00126 00009 folio 254 galley 6
C00150 00010 folio 259 galley 7
C00163 ENDMK
C⊗;
folio 223 galley 1E
0 {U0}{H10L12M29}58320#Computer Programming!(Knuth/A-W)!f.
2 223!g. 1E!ch 3|'{H9L11}|π|≡3|≡8|≡.|9|4[|εM|*/|↔M|↔m|\]
6 |π(A. N. Kolmogorov.) Given |εN, n |πand |ε|≤e
14 |πwhat is the smallest number of algorithms in
22 a set |≡A such that no |ε(n,|4|≤e)-|πrandom binary
30 sequences of length |εN |πexist with respect
37 to |≡A? (If exact formulas cannot be given, can
46 asymptotic formulas be found? The point of this
54 problem is to discover how close the bound (35)
63 comes to being ``best possible.'')|'{A3}|≡3|≡9|≡.|9|4[|εHM|*/
68 |↔M|↔C|\] (|πW. M. Schmidt.) Let |εU|βn |πbe
75 a [0,|41) sequence, and let |ε|≤n|βn(u) |πbe
82 the number of nonnegative integers |εj|4|¬E|4n
88 |πsuch that |ε0|4|¬W|4U|βj|4|¬E|4u. |πProve that
93 there is a positive constant |εc |πsuch that,
101 for any |εN |πand for any [0,|41) sequence |↔b|εU|βn|↔v,
110 |πwe have|'{A9}|¬G|ε|≤n|βn(u)|4α_↓|4un|¬G|4|¬Q|4c|4|πlog|4|ε
112 N|;{A9}|πfor some |εn |πand |εu |πwith |ε0|4|¬E|4n|4|¬W|4N,
120 0|4|¬E|4u|¬W|41. |π(In other words, no [0,|41)
126 sequence can be |εtoo |πequidistributed.)|'{A3}|≡4|≡1|≡.|9|4
131 [|ε|*/|↔O|↔o|\] |π(I. J. Good.) Can a valid table
139 of random digits contain just one misprint?|'
146 {A24}{H10L12M29}|∨3|∨.|∨6|∨.|9|4|∨S|∨U|∨M|∨M|∨A|∨R|∨Y|'
147 {A12}We have covered a fairly large number of
155 topics in this chapter: how to generate random
163 numbers, how to test them, how to modify them
172 in applications, and how to derive theoretical
179 facts about them. Perhaps the main question in
187 many raders' minds will be, ``What is the result
196 of all this theory? What is a simple, virtuous,
205 random-number generator I can use in my programs
213 in order to have a reliable source of random
222 numbers?''|'!|4|4|4|4The detailed investigations
226 in this chapter suggest that the following procedure
234 gives the ``nicest'' and ``simplest'' random-number
240 generator for the machine language of must computers:
248 At the beginning of the program, set an integer
257 variable |εX |πto some value |εX|β0. |πThis variable
265 |εX |πis to be used only for the purpose of random-number
276 generation. Whenever a new random number is required
284 by the program, set|'{A9}|εX|4|¬L|4(aX|4α+↓|4c)|πmod|4|εm|J!
288 (1)|;{A9}|πand use the new value of |εX |πas
297 the random value. It is necessary to choose |εX|β0,
306 a, c, |πand |εm |πproperly, and to use the random
316 numbers widely, according to the following principles:|'
323 !|4|4|4|4i)|9|4The ``seed'' number |εX|β0 |πmay
328 be chosen arbitrarily. If the program is run
336 several times and a di=erent source of random
344 numbers is desired each time, set |εX|β0 |πto
352 the last value attained by |εX |πon the preceding
361 run; or (if more convenient) set |εX|β0 |πto
369 the current date and time. If the program may
378 need to be rerun later with the |εsame |πrandom
387 numbers (e.g., when debugging), be sure to print
395 out |εX|β0 |πif it isn't otherwise known.|'!|4|4|4|4ii)|9|4T
402 he number |εm |πshould be large, say at least
411 2|g3|g0. It may conveniently be taken as the
419 computer's word size, since this makes the computation
427 of |ε(aX|4α+↓|4c)|πmod|4|πm quite e∃cient. Section
432 3.2.1.1 discusses the choice of |εm |πin more
440 detail. The computation of |ε(aX|4α+↓|4c)|πmod
445 |εm |πmust be done |εexactly, |πwith no roundo=
453 error.|'!|4|4|4|4iii)|9|4If |εm |πis a power
459 of 2 (i.e., if a binary computer is being used),
469 pick |εa |πso that |εa |πmod 8|4α=↓|45. If |εm
478 |πis a power of 10 (i.e., if a decimal computer
488 is being used), choose |εa |πso that |εa|4|πmod|4200|4α=↓|42
495 1. This choice of |εa |πtogether with the choice
504 of |εc |πgiven below ensures that the random-number
512 generator will produce all |εm |πdi=erent possible
519 values of |εX |πbefore it starts to repeat (see
528 Section 3.2.1.2) and ensures high ``potency''
534 (see Section 3.2.1.3).|'!|4|4|4|4iv)|9|4The multiplier
539 |εa |πshould preferably be chosen between .01|εm
546 |πand .99|εm, |πand its binary or decimal figits
554 should |εnot |πhave a simple, regular pattern.
561 By choosing some haphazard constant like |εa|4α=↓|4314159262
567 1 |π(which satis_es both of the conditions in
575 (iii){H12}){H10}, one almost always obtains a
581 reasonably good multiplier. Further testing should
587 of course be done if the random-number generator
595 is to be used extensively; for example, there
603 should be no large quotients when Euclid's algorithm
611 is used to _nd the gcd of |εa |πand |εm |π(see
622 Section 3.3.3). The multiplier should pass the
629 spectral test (Section 3.3.4) and several tests
636 of Section 3.3.2 before it is considered to have
645 a truly clean bill of health.|'!|4|4|4|4v)|9|4The
652 value of |εc |πis immaterial when |εa |πis a
661 good multiplier, except that |εc |πmust have
668 no factor in common with |εm. |πThus we may choose
678 |εc|4α=↓|41 |πor |εc|4α=↓|4a.|'|π!|4|4|4|4vi)|9|4The
682 least signi_cant (right-hand) digits of |εX |πare
689 not very random, so decisions based on the number
698 |εX |πshould always be primarily in⊗uenced by
705 the most signi_cant digits. It is generally best
713 to think of |εX |πas a random fraction |εX/m
722 |πbetween 0 and 1, that is, to visualize |εX
731 |πwith a decimal point at its left, than to regard
741 |εX |πas a random integer between 0 and |εm|4α_↓|41.
750 |πTo compute a random integer between 0 and |εk|4α_↓|41,
759 |πone should multiply by |εk |πand truncate the
767 result (see the beginning of Section 3.4.2).|'
774 !|4|4|4|4vii)|9|4An important limitation on the
779 randomness of sequence (1) is discussed in Section
787 3.3.4, where it is shown that the ``accuracy''
795 in |εt |πdimensions will be only about one part
804 in |ε|¬H|v4m|). |πMonte Carlo applications requiring
810 higher resolution can improve the randomness
816 by employing techniques discussed in Section
822 3.2.2.|'!|4|4|4|4The above comments apply primarily
828 to machine-language coding. In higher-level programming
834 languages, we are often unable to use such machine-dependent
842 features as integer arithmetic modulo the word
850 size, and careful compilers will not allow us
858 to compute the product of two large integers.
866 Another technique which we migh call the |εsubtractive
874 method |π(exercise 3.2.223) can be used to provide
882 a ``portable'' random number generator which
888 is e∃ciently describable in any higher-level
894 programming language, since it makes use only
901 of integer arithmetic between |→α_↓10|g9 and
907 10|g9. Here is how the subtractive method light
915 be coded in FORTRAN, as a subroutine which delivers
924 an array of 55 random integers at once:|'{A9}{H9L11M29}!!|9|
932 4|¬f|¬u|¬n|¬c|¬t|¬i|¬o|¬n |¬i|¬r|¬n|¬5|¬5|≤#|¬i|¬a|≤&|'
934 !!|4|9|¬d|¬i|¬m|¬e|¬n|¬s|¬i|¬o|¬n |¬i|¬a|≤#|¬1|≤&|'
936 |¬c!!|1|1|¬a|¬s|¬s|¬u|¬m|¬i|¬n|¬g |¬t|¬h|¬a|¬t
938 |¬i|¬a|≤#|¬1|≤&|¬,|4.|4.|4.|4.|4|¬,|4|¬i|¬a|≤#|¬5|¬5|≤&
939 |¬h|¬a|¬v|¬e |¬b|¬e|¬e|¬n |¬s|¬e|¬t |¬u|¬p |¬p|¬r|¬o|¬p|¬e|¬
943 r|¬l|¬y|'|¬c!!|1|1|¬t|¬h|¬i|¬s |¬s|¬u|¬b|¬r|¬o|¬u|¬t|¬i|¬n|¬
945 e |¬r|¬e|¬s|¬e|¬t|¬s |¬t|¬h|¬e |¬i|¬a |¬a|¬r|¬r|¬a|¬y
950 |¬t|¬o |¬t|¬h|¬e |¬n|¬e|¬x|¬t |¬5|¬5 |¬n|¬u|¬m|¬b|¬e|¬r|¬s|'
955 |¬c!!|1|1|¬o|¬f |¬a |¬p|¬s|¬e|¬u|¬d|¬o-|¬r|¬a|¬n|¬d|¬o|¬m
958 |¬s|¬e|¬q|¬u|¬e|¬n|¬c|¬e|¬, |¬a|¬n|¬d |¬r|¬e|¬t|¬u|¬r|¬n|¬s
961 |¬t|¬h|¬e |¬v|¬a|¬l|¬u|¬e |¬1.|'!!|4|9|¬d|¬o
965 |¬1 |¬i|≤$|¬1|¬, |¬2|¬4|'!!|4|9!|¬j|≤$|¬i|¬a|≤#|¬i|≤%|¬3|¬1|
968 ≤&|'!!|4|9!|¬i|¬f |≤#|¬j.|¬l|¬t.|¬o|≤& |¬j|≤$|¬j|≤%|¬1|¬0|¬0
971 |¬0|¬0|¬0|¬0|¬0|¬0|¬0|'|4|4|4|4|4|¬1!!|¬i|¬a|≤#|¬i|≤&|≤$|¬j|
972 '!!|4|9|¬d|¬o |¬2 |¬i|≤$|¬2|¬5|¬, |¬5|¬5|'!!!|9|4|¬j|≤$|¬i|¬
977 a|≤#|¬i|≤#|≤*/|¬i|¬a|≤#|¬i|≤*/|¬2|¬4|≤&|'!!!|4|9|¬i|¬f
979 |≤#|¬j .|¬l|¬t. |¬0|≤& |¬j|≤$|¬j|≤%|¬1|¬0|¬0|¬0|¬0|¬0|¬0|¬0|
982 ¬0|¬0|'|4|4|4|4|4|¬2!!|¬i|¬a|≤#|¬i|≤&|≤$|¬j|'
984 !!|9|4|¬i|¬r|¬n|¬5|¬5|≤$|¬1|'!!|9|4|¬r|¬e|¬t|¬u|¬r|¬n|'
986 !!|9|4|¬e|¬n|¬d|'{A9}{H10L12M29}To use these
990 numbers in a FORTRAN program, let |¬j|¬r|¬a|¬n|¬d
997 be an auxiliary integer variable; we may obtain
1005 the next random number |¬u (as a fraction between
1014 0 and 1) by writing the following three statements:|'
1023 {A9}{H9L11}!!|9|4|¬j|¬r|¬a|¬n|¬d|≤$|¬j|¬r|¬a|¬n|¬d|≤%|¬1|'
1024 !!|9|4|¬i|¬f |≤#|¬j|¬r|¬a|¬n|¬d .|¬g|¬t. |¬5|¬5|≤&
1028 |¬j|¬r|¬a|¬n|¬d|≤$|¬i|¬r|¬n|¬5|¬5|≤#|¬i|¬a|≤&|'
1029 !!|9|4|¬u|≤$|¬f|¬l|¬o|¬a|¬t|≤#|¬i|¬a|≤#|¬j|¬r|¬a|¬n|¬d|≤&|≤&
1029 !|¬1.|¬0|¬e|≤*/|¬9|'{A9}{H10L12M29}At the beginning
1033 of our program we write ``|¬d|¬i|¬m|¬e|¬n|¬s|¬i|¬o|¬n
1039 |¬i|¬a|≤#|¬5|¬5|≤&'' and ``|¬j|¬r|¬a|¬n|¬d|≤$|¬5|¬5''
1042 and we must also initialize the |¬i|¬a array.
1050 Appropriate initialization can be done by calling
1057 the following subroutine with |¬i|¬x set to any
1065 integer value (selected like |εX|β0 |πin rule
1072 (i) above, preferably large):|'{A9}{H9L11}!!|9|4|¬s|¬u|¬b|¬r
1076 |¬o|¬u|¬t|¬i|¬n|¬e |¬i|¬n|¬5|¬5|≤#|¬i|¬a|¬,|¬i|¬x|≤&|'
1078 |¬c!!|1|1|¬t|¬h|¬i|¬s |¬s|¬u|¬b|¬r|¬o|¬u|¬t|¬i|¬n|¬e
1080 |¬s|¬e|¬t|¬s |¬i|¬a|≤#|¬1|≤&|4.|4.|4.|4|¬i|¬a|≤#|¬5|¬5|≤&
1082 |¬t|¬o |¬s|¬t|¬a|¬r|¬t|¬i|¬n|¬g |¬v|¬a|¬l|¬u|¬e|¬s|'
1085 |¬c!!|1|1|¬s|¬u|¬i|¬t|¬a|¬b|¬l|¬e |¬f|¬o|¬r |¬l|¬a|¬t|¬e|¬r
1088 |¬c|¬a|¬l|¬l|¬s |¬o|¬n |¬i|¬r|¬n|¬5|¬5|≤#|¬i|¬a|≤&.|'
1091 |¬c!!|1|1|¬i|¬x |¬i|¬s |¬a|¬n|¬y |¬i|¬n|¬t|¬e|¬g|¬e|¬r
1095 ``|¬s|¬e|¬e|¬d'' |¬v|¬a|¬l|¬u|¬e |¬b|¬e|¬t|¬w|¬e|¬e|¬n
1098 |¬0 |¬a|¬n|¬d |¬1|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0.|'
1101 !!|9|4|¬i|¬a|≤#|¬5|¬5|≤&|≤$|¬i|¬x|'!!|9|4|¬j|≤$|¬i|¬x|'
1103 !!|9|4|¬k|≤$|¬1|'!!|9|4|¬d|¬o |¬1 |¬i|≤$|¬1|¬,
1107 |¬5|¬4|'!!!|9|4|¬i|¬i|≤$|¬m|¬o|¬d|≤#|¬2|¬1{J3}|≤⊃|¬i|¬,
1109 |¬5|¬5|≤&|'!!!|9|4|¬i|¬a|≤#|¬i|¬i|≤&|≤$|¬k|'!!!|9|4|¬k|≤$|¬j
1111 |≤*/|¬k|'!!!|9|4|¬i|¬f|≤$|≤#|¬k .|¬l|¬t. |¬0|≤&|¬k|≤$|¬k|≤%|¬
1114 1|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0|¬0|'!!!|9|4|¬j|≤$|¬i|¬a|≤#|¬i|¬i|≤
1115 &|'|4|4|4|4|4|¬1!|¬c|¬o|¬n|¬t|¬i|¬n|¬u|¬e|'!!|9|4|¬r|¬e|¬t|¬
1117 u|¬r|¬n|'!!|9|4|¬e|¬n|¬d|'{A9}{H10L12M29}(This
1120 subroutine computes a Fibonacci-like sequence;
1125 multiplication of indices by 21 spreads the values
1133 around so as to alleviate initial nonrandomness
1140 problems such as those in exercise 3.2.2<2. Note
1148 that 2|g2|g9|4|¬W|410|g9|4|¬W|42|g3|g0; any large
1152 even number may actually be substituted for 10|g9
1160 in these rountines, if a corresponding change
1167 is made in the computation of the random fraction
1176 |¬u. The numbers (24,|455) may be replaced by
1184 any pair of values |ε(j, k) |πin Table 3.2.2<1,
1193 for |εk|4|¬R|450; |πthe constants 31, 25, 54,
1200 21 should then be replaced by |εk|4α_↓|4j, j|4α+↓|41,
1208 k|4α_↓|41, |πand |εd |πrespectively, where |εd
1214 |πis relatively prime to |εk |πand |εd|4|¬V|4k/|≤f|g2.)|'
1221 |π!|4|4|4|4Although a great deal is known about
1228 linear congruential sequences like (1), very
1234 little has yet been proved about the randomness
1242 properties of the subtractive method. Both approaches
1249 seem to be reliable in practice.|'!|4|4|4|4Unfortunately,
1256 quite a bit of published material in existence
1264 at the time this chapter was written recommends
1272 the use of generators which violate the suggestion
1280 above; and the most common generator in actual
1288 use, |¬r|¬a|¬n|¬d|¬u, is really horrible (cf.
1294 Section 3.3.4). The authors of many contributions
1301 to the science of random-number generation were
1308 unaware that particular methods they were advocating
1315 would prove to be inadequate.|'|H*?*?{U0}{H10L12M29}58320#Comp
folio 229 galley 2E NOTE:Middle and end of this galley couldn't be read.
1320 uter Programming!(Knuth/A.-W)!f. 229!ch. 3!g.
1324 2E|'{A12}!|4|4|4|4Excellent bibliographies of
1328 the pre-1972 literature on random-number generation
1334 have been compiled by Richard E. Nance and Claude
1343 Overstreet, Jr., |εComputing Reviews |≡1|≡3 |π(1972),
1349 495<508, and by E. R. Sowey, |εInternational
1356 Stat. Review |≡4|≡0 |π(1972), 355<371. For further
1363 study, especially with respect to |εa priori
1370 |πtheoretical tests, see the book |εUniform Random
1377 Numbers |πby U. Dieter and J. H. Ahrens (New
1386 York: Wiley, 1975).|'!|4|4|4|4For a detailed
1392 study of the use of random numbers in numerical
1401 analysis, see J. M. Hammersley and D. C. Handscomb,
1410 |εMonte Carlo Methods (|πLondon: Methuen, 1964).
1416 This book shows that many numerical methods are
1424 enhanced by using numbers which are ``quasirandom,''
1431 designed speci_cally for a certain purpose (not
1438 necessarily satisfying the statistical tests
1443 we have discussed).|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'
1447 {A12}{H9L11M29}|9|1|≡1|≡.|9|4[|ε|*/|↔P|↔O|\] |πWrite
1449 a |¬m|¬i|¬x subroutine with the following characteristics,
1456 using method (1):|'{A9}|h|π!!|1|1Entry|4|1conditions:!!|∂oip
1459 lokoikju|E|n|'!!|1|1Calling|4|1sequence:|L|¬j|¬m|¬p!|¬r|¬a|¬
1460 n|¬d|¬i>!!|1|1Entry|4|1conditions:!!rA|4α=↓|4|εk,
1462 |πa positive integer|4|¬W|45000|'!!|1|1Exit|4|1conditions:|L
1465 rA|4|¬L|4a random integer |εY, 1|4|¬E|4Y|4|¬E|4k,
1470 |πwith each integer>|Lequally probable; rX|4α=↓|4?;
1476 over⊗ow o=.|'{A3}|9|1|≡2|≡.|9|4[|ε|*/|↔P|↔O|\]
1479 |πSome people have been afraid computers will
1486 someday take over the world; but they are reassured
1495 by the statement that a machine cannot do anything
1504 really new, since it is only obeying the commands
1513 of its master, the programmer. Lady Lovelace
1520 wrote in 1844, ``The Analytical Engine has no
1528 pretensions to |εoriginate |πanything. It can
1534 do |εwhatever we know how to ordr it |πto perform.''
1544 Her statement has been further elaborated by
1551 many philosophers. |πDiscuss this topic, with
1557 random-number generators in mind.|'{A3}|9|1|≡3|≡.|9|4[|ε|*/|↔
1561 L|↔P|\] (A dice game.) |πWrite a program that
1569 simulates a roll of two dice, each of which takes
1579 on the values 1, 2,|4.|4.|4.|4, 6 with equal
1587 probability. If the total is 7 or 11 on the _rst
1598 roll, the game is won; a total of 2, 3, or 12
1610 loses; and on any other total, call that total
1619 the ``point'' and continue rolling dice until
1626 either a 7 occurs (a loss) or the point occurs
1636 again (a win).|'!!|1|1Play ten games. The result
1644 of each roll of the dice should be printed in
1654 the form |εmn, |πwhere |εm |πand |εn |πare the
1663 contents of the two dice, followed by some appropriate
1672 comment (like ``snake eyes'' or ``little Joe''
1679 or ``the hard way,'' etc.)|'{A3}|9|1|≡4|≡.|9|4[|ε|*/|↔M|↔c|\]
1684 (Solitaire or patience.) |πSome people spend
1691 a lot of valuable time playing card games of
1700 solitaire, and perhaps automation will make an
1707 important inroad in this area. Write a program
1715 that (a) shu+es a simulated deck of cards; (b)
1724 plays some common game of solitaire based on
1732 the order of the cards in the deck; (c) prints
1742 out the result of the game, i.e., how close the
1752 program came to winning. Several games should
1759 be played. The program might be set up to ``cheat''
1769 upon request.|'{A3}|9|1|≡5|≡.|9|4[|ε|*/|↔M|↔o|\]
1772 (Creative writing by computer.) |πA television
1778 program entitled ``The Thinking Machine,'' broadcast
1784 by the CBS television network on October 26,
1792 1960, featured (among other things) two Western-style
1799 playlets which were written by a computer program.
1807 Here are the two scipts as they were printed
1816 by the computer:|'{A9}|E|'|}|O{H8L9M29}|*/Saga
1821 |9|4|\1.|9|4(The gun is in the right hand; the
1829 money is in the left hand; the glass is on the
1840 table; the bottle is on the table; the holster
1849 is on the robber; the sheri='s gun is in the
1859 sheri='s right hand; the sheri='s holster is
1866 on the sheri=.)|'{I3.5H}ROBBER;|9|4(The robber
1871 is at the window.) Go to door; open door; go
1881 thru door; close door; go to corner; put money
1890 down at corner; go to table; put gun on table;
1900 sit and _dgit; sit at table; pick up glass with
1910 right hand (empty); put glass on table; pick
1918 up bottle with right hand; pour; put bottle on
1927 table; pick up glass with right hand; take a
1936 drink from glass; put glass on table;{A3}SHERIFF:|9|4(The
1943 sheri= is at the window.) See robber; (robber
1951 sees sheri=); go to door.|'{A3}ROBBER:|9|4Put
1957 glass on table; pick up gun with right hand;
1966 check gun.|'{A3}SHERIFF:|9|4Wait; open door;
1971 see robber; (robber sees sheri=); go thru door.|'
1979 {A3}ROBBER:|9|4Go to window; aim; _re; SHERIFF
1985 NICKED.|'{A3}SHERIFF:|9|4Go to window; aim; _re;
1991 MISSED; go to door; go to window.|'{A3}ROBBER:|9|4Go
1999 to door; aim; aim.|'{A3}Sheriff:|9|4Aim; _re;
2005 MISSED.|'{A3}ROBBER:|9|4Fire; SHERIFF NICKED.|'
2009 {A3}SHERIFF:|9|4Go to door; aim; _re; MISSED;
2015 go thru door; aim.|'{A3}ROBBER:|9|4Aim; _re;
2021 MISSED; aim; _re; MISSED.|'{A3}SHERIFF:|9|4Fire;
2026 MISSEDROBBER:|9|4Drop gun; robber dies.|'|*/Saga
2031 |9|4|\2.|9|4(The gun is in the right hand; the
2039 money is in the left hand; the glass is on the
2050 table; the bottle is on the table; the holster
2059 is on the robber; the sheri='s gun is in the
2069 sheri='s right hand; the sheri='s holster is
2076 on the sheri=.)|'{A3}{I3.5H}ROBBER:|9|4(The robber
2081 is at the window.) Go to door; open door; go
2091 thru door; close door; go to corner; put money
2100 down at corner; go to window; put gun down at
2110 window; lean on window and look; lean on window
2119 and look; go to corner; count money; go to table;
2129 pick up glass with right hand (empty); take glass
2138 from right hand with left hand; pick up bottle
2147 with right hand; pour; put bottle on table; take
2156 glass from left hand with right hand; take a
2165 drink from glass; put glass on table; pick up
2174 bottle with right hand; pour; go to corner; put
2183 bottle down at corner; to to window; pick up
2192 gun with right hand; check gun; put gun in holster;
2202 go to table; pick up glass with right hand; take
2212 a dr*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
2213
folio 234 galley 1
0 {U0}{H10L12M29}|π58320#Computer Programming!(Knuth/Addison-W
1 esley)!f. 234!ch. 4!g. 1|'{A12}{H11L12}|!C|1|1|!H|4|!A|2|!P|
5 2|!T|2|!E|2|!R|9|1|!F|2|!O|2|!U|2|!R|'{A46}{H20L20}|∨A|∨R|∨I
6 |∨T|∨H|∨M|∨E|∨T|∨I|∨C|?{A12}{H8L11}|E|'|}|O{H8L11M29}|*/Seein
8 g there is nothing (right well beloved Students
16 in the Mathematickes)|?that is so troublesome
23 to Mathematicall practise, nor that doth more
30 molest|?and hinder Calculators, then the Multiplications,
37 Divisions, square and|?cubical Extractions of
43 great numbers, which besides the tediuus expence
50 of|?time are for the most part subject to many
60 slippery errors. I began therefore|?to consider
67 in my minde, by what certaine and ready Art I
77 might|?remove those hindrances.|?{A6}|\#JOHN
82 NAPIER (1614)|?{A11}|*/I do hate sums. There is
90 no greater mistake than to call arithmetic an
98 exact|?science. There are|4.|4.|4.|4hidden laws
103 of number which it requires a mind|?like mine
112 to perceive. For instance, if you add a sum from
122 the bottom up,|?and then again from the top down,
132 the result is always di=erent.|?{A6}|\#MRS. LA
139 TOUCHE (19th century)|?{A11}|*/I cannot conceive
145 that anybody will require multiplications at
151 the rate|?of 40,000, or even 4,000 per hour;
160 such a revolutionary change as the|?octonary
167 scale should not be imposed upon mankind in general|?
176 for the sake of a few individuals.|?{A6}|\#F.
184 H. WALES (1936)|?{A38}|!|E|'|{{H10L12M29}|πThe
189 chief purpose of this chapter is to make a careful
199 study of the four basic processes of arithmetic:
207 addition, subtraction, multiplication, and division.
212 Many people regard arithmetic as a trivial thing
220 which children learn and computers do, but we
228 will see that artihmetic is an intriguing topic
236 with many interesting facets. It is important
243 to make a thorough study of e∃cient methods for
252 calculating with numbers, since arithmetic underlies
258 so many computer applications.|'!|9|7Arithmetic
263 is, in fact, a lively subject which has played
272 an important part in the history of the world,
281 and it still is undergoing rapid development.
288 In this chapter, we will analyze algorithms for
296 doing arithmetic operations on many types of
303 quantities, such as ``⊗oating-point'' numbers,
308 extremely large numbers, fractions (rational
313 numbers), polynomials, and power series; and
319 we will also discuss related topics such as radix
328 conversion, factoring of numbers, and the evaluation
335 of polynomials.|'{A24}|∨4|∨.|∨1|∨.|9|∨P|∨O|∨S|∨I|∨T|∨I|∨O|∨N
337 |∨A|∨L|9|∨N|∨U|∨M|∨B|∨E|∨R|9|∨S|∨Y|∨S|∨T|∨E|∨M|∨S|'
338 {A12}The way we do arithmetic is intimately related
346 to the way we represent the numbers we deal with,
356 so it is appropriate to begin our study of arithmetic
366 with a discussion of the principal means for
374 representing numbers.|'!|9|7Positional notation
378 using base |εb |π(alternatively called |εradix
384 b) |πis de_ned by the rule|'{A9}|ε(.|4.|4.|4a|β3a|β2a|β1a|β0
390 .a|βα_↓|β1a|βα_↓|β2|4.|4.|4.)|βb|'α=↓|4|¬O|4|¬O|4|¬O|4α+↓|4a
391 |β3b|g3|4α+↓|4a|β2b|g2|4α+↓|4a|β1b|g1|4α+↓|4a|β0|4α+↓|4a|βα_
391 ↓|β1b|gα_↓|g1|4α+↓|4a|βα_↓|β2b|gα_↓|g2|4α+↓|4|¬O|4|¬O|4|¬O|4
391 ;!(1)|?{A9}|πfor example, (520.3)|β6|4α=↓|45|4|¬O|46|g2|4α+↓
394 |42|4|¬O|46|g1|4α+↓|40|4α+↓|43|4|¬O|46|gα_↓|g1|4α=↓|4192|f1|
394 d32|). Our conventional decimal number system
400 is, of course, the special case when |εb |πis
409 ten, and when the |εa'|πs are chosen from the
418 ``decimal digits'' 0, 1, 2, 3, 4, 5, 6, 7, 8,
429 9; in this case the subscript |εb |πin (1) may
439 be omitted.|'!|9|6The simplest generalizations
444 of the decimal number dystem are obtained when
452 we take |εb |πto be an integer greater than 1
462 and when we require the |εa'|πs to be integers
471 in the range 0|4|¬E|4|εa|βk|4|¬W|4b. |πThis gives
477 us the standard binary |ε(b|4α=↓|42), |πternary
483 |ε(b|4α=↓|43), |πquaternary |ε(b|4α=↓|44), |πquinary
487 |ε(b|4α=↓|45), . . . |πnumber systems. In general,
495 we could take |εb |πto be any number, and we
505 could choose the |εa'|πs from any speci_ed set
513 of numbers; this leads to some interesting situations,
521 as we shall see.|'!|9|7The dot which appears
529 between |εa|β0 |πand |εa|βα_↓|β1 |πin (1) is
536 called the |εradix point. |π(When |εb|4α=↓|410,
542 |πit is also called the decimal point, and when
551 |εb|4α=↓|42, |πit is sometimes called the binary
558 point, etc.) Europeans often use a comma instead
566 of a dot to denote the radix point; Englishmen
575 often use a raised dot.|'!|9|7The |εa'|πs in
583 (1) are called the |εdigits |πof the representation.
591 A digit |εa|βk |πfor large |εk |πis often said
600 to be ``more signi_cant'' than the digits |εa|βk
608 |πfor small |εk; |πaccordingly, the leftmost
614 or ``leading'' digit is referred to as the |εmost
623 signi⊂cant digit. |πIn the standard binary system
630 the binary digits are often called |εbits. |πIn
638 the standard hexadecimal system (radix sixteen)
644 the hexadecimal digits zero through _fteen are
651 usually denoted by|'{A9}|¬0|¬,|¬1|¬,|¬2|¬,|¬3|¬,|¬4|¬,|¬5|¬,
654 |¬6|¬,|¬7|¬,|¬8|¬,|¬9|¬,|¬a|¬,|¬b|¬,|¬c|¬,|¬d|¬,|¬e|¬,|¬f.|;
655 {A9}!|9|7The historical development of number
660 representations is a fascinating story, since
666 it parallels the development of civilization
672 itself. We would be going far a_eld is we were
682 to examine this history in minute detail, but
690 it will be instructive to look at its main features
700 here:|'!|9|7The earliest forms of number representations,
707 still found in primitive cultures, are generally
714 based on groups of _ngers, or piles of stones,
723 etc., usually with special conventions about
729 replacing a larger pile or group of, say, _ve
738 or ten objects by one object of af special kind
748 or in a special place. Such systems lead naturally
757 to the earliest ways of representing numbers
764 in written form, as in the systems of Babylonian,
773 Egyptian, Greek, Chinese, and Roman numerals,
779 but such notations are quite inconvenient for
786 performing arithmetic operations except in the
792 simplest cases.|'!|9|6During the twentieth century,
798 historians of mathematics have made extensive
804 studies of early cuneiform tablets found by archeologists
812 in the Middle East. These studies show that the
821 Babylonian people actually had two distinct systems
828 of number representation: Numbers used in everyday
835 business transactions were written in a notation
842 based on grouping by tens, hundreds, etc.; this
850 notation was inherited fromm earlier Mesopotamian
856 civilizations, and large numbers were seldom
862 required. When more di∃cult mathematical problems
868 were considered, however, Ba↓bylonian mathematicians
873 made extensive use of a sexagesimal (radix sixty)
881 positional notation which was highly developed
887 at least as early as 1750 {H7}B{H10}.{H7}C{H10}.
894 This notation was unique in that it was actually
903 a |ε⊃oating-point |πform of representation with
909 exponents omitted; the proper scale factor or
916 power of sixty was to be supplied by the context,
926 so that, for example, the numbers 2, 120, 7200,
935 |f1|d330|), etc. were all written in an identical
943 manner. The notation was especially convenient
949 for multiplication and division, using auxiliary
955 tables, since radix-point alignment had no e=ect
962 on the answer. As examples of this Babylonian
970 notation, consider the following excerpts from
976 early tables: The square of 30 is 15 (which may
986 also be read, ``The square of |f1|d32|) is |f1|d34|)'');
995 the reciprocal of 81|4α=↓|4(1|421)|β6|β0 is (44|426|440)|β6|
1000 β0; and the square of the latter is (32|455|418|431|46|440)|
1008 β6|β0. The Babylonians had a symbol for zero,
1016 but because of their ``⊗oating-point'' philosophy,
1022 it was used only within numbers, not at the right
1032 end to denote a scale factor. For the interesting
1041 story of early Babylonian mathematics, see O.
1048 Neugebauer, |εThe Exact Sciences in Antiquity
1054 |π(Princeton University Press, 1952), and B.
1060 L. van der Waerden, |εScience Awakening, |πtr.
1067 by A. Dresden (Groningen: P. Noordho=, 1954);
1074 see also D. E. Knuth, |εCACM |π|≡1|≡5 (1972),
1082 671<677.|'!|9|7Fixed-point positional notation
1086 was apparently developed _rst by the Maya Indians
1094 in central America 2000 years ago; their radix
1102 20 system was highly developed, especially in
1109 connection with astronomical records and calendar
1115 dates. But the Spanish conquerors destroyed nearly
1122 all of the Maya books on history and science,
1131 so we do not know how sophisticated they had
1140 become at arithmetic; some special-purpose multiplication
1146 tables have been found, but no examples of division
1155 are known [cf. J. Eric S. Thompson, |εContributions
1163 to Amer. Anthropology and History |≡7 (|πCarnegie
1170 Inst. of Washington, 1942), 37<62].|'!|9|7Several
1176 centuries before Christ, the Greek people employed
1183 an early form of the abacus to do their arithmetical
1193 calculations, using sand and/or pebbles on a
1200 board wwhich had rows or columns corresponding
1207 in a natural way to our decimal system. It is
1217 perhals surprising to us that the same positional
1225 notation was never adapted to written forms of
1233 numbers, since we are so accustomed to reckoning
1241 with the decimal system using penicl and paper;
1249 but the greater ease of calculating by abacus
1257 (since handwriting was not a common skill, and
1265 since abacus calculations makes it unnecessary
1271 to memorize addition and multiplication tables)
1277 probably made the Greeks feel it would be sil{U0}{H10L12M29}
folio 237 galley 2
1285 |π58320#Computer Programming!(Knuth/Addison-Wesley)!f.
1287 237!ch. 4!g. 2|'{A6}!|9|6Our decimal notation,
1293 which di=ers from the more ancient forms primarily
1301 because of its _xed radix point, together with
1309 its symbol for zero to mark an empty position,
1318 was developed _rst in India among the Hindu people.
1327 The exact date when this notation _rst appeared
1335 is quite uncertain; about 600 {H7}A{H10}.{H7}D{H10}.
1341 seems to be a good guess. Hindu science was rather
1351 highly developed at that time, particularly in
1358 astronomy. The earliest known Hindu manuscripts
1364 which show this notation have numbers written
1371 backwards (with the most signi_cant digit at
1378 the right), but soon it became standard to put
1387 the most signi_cant digit at the left.|'!|9|7About
1395 750 {H7}A{H10}.{H7}D{H10}., the Hindu principles
1400 of decimal arithmetic were brought to Persia,
1407 as several important works were translated into
1414 Arabic; a picturesque account of this development
1421 is given in a Hebrew document, which has been
1430 translated into English in |εAMM |≡1|≡5 (1918),
1437 99<108. |πNot long after this, al-Khow|=7arizm|=7↓|Z
1443 wrote his Arabic textbook on the subject. (As
1451 noted in Chapter 1, our word ``algorithm'' comes
1459 from al-Khow|=7arizm|=7↓|Z's name.) His book
1464 was translated into Latin and was a strong in⊗uence
1473 on Leonardo Pisano (Fibonacci), whose book on
1480 arithmetic (1202 {H7}A{H10}.{H7}D{H10}.) played
1484 a major role in the spreading of Hindu-Arabic
1492 numerals into Europe. It is interesting to note
1500 that the left-to-right order of writing numbers
1507 was unchanged during these two transitions from
1514 Hindu to Arabic and from Arabic to Latin, although
1523 Arabic is written from right to left while Hindu
1532 and Latin are written from left to right. A detailed
1542 account on the subsequent propagation of decimal
1549 numeration and arithmetic into all parts of Europe
1557 during the period from 1200 to 1600 {H7}A{H10}.{H7}D{H10}.
1565 is given by David Eugene Smith in his|εHistory
1573 of Mathematics |≡1 |π(Boston: Ginn and Co., 1923),
1581 Chapers 6 and 8.|'!|9|7Decimal notation was applied
1589 at _rst only to integer numbers, not to fractions.
1598 Arabic astronomers, who required fractions in
1604 their star charts and other tables, continued
1611 to use the notation of Ptolemy (the famous Greek
1620 astronomer) which was based on sexagesimal fractions.
1627 This system still survives today, in our trigonometric
1635 units of ``degrees, minutes, and seconds,'' and
1642 also in our units of time, as a remnant of the
1653 original Babylonian sexagesimal notation. Early
1658 European mathematicians also used sexagesimal
1663 fractions when dealing with noninteger numbers;
1669 for example, Fibonacci gave the value|'{A9}1|¬P|922|¬S|97|¬P
1675 |942|9|9ee|ε|gI|gV|94|gV|940|gV|gI|;{A9}|πas
1677 an approximation to the root of the equation
1685 |εx|g3|4α+↓|42x|g2|4α+↓|410x|4α=↓|420. |π(The
1687 correct answer is 1|¬0 22|¬S 7|¬C 42|9 33|ε|gI|gV
1695 4|gV 38|gV|gI 30|gV|gI|gI 50|gV|gI|gI|gI 15|gI|gX
1700 43|gX|4.|4.|4.|4.)|'|π!|9|7The use of decimal
1705 notation also for tenths, hundredths, etc., in
1712 a similar way seems to be a comparatively minor
1721 change; but, of course, it is hard to break with
1731 tradition, and sexagesimal fractions have an
1737 advantage over decimal fractions in that numbers
1744 such as |f1|d33|) can be expressed exactly in
1752 a simple way. Chinese mathematicians (who never
1759 used sexagesimals) were the _rst people to work
1767 with the equivalent of decimal fractions, although
1774 their numeral system (lacking zero) was not originally
1782 a positional number system in the strict sense.
1790 Chinese units of weights and measures were decimal,
1798 so that Tsu Chhung-Chih (who died c.500 {H7}A{H10}.{H7}D{H10
1805 }. was able to express an approximation to |ε|≤p
1814 |πas ``3 chang, 1 chhih, 4 tshun, 1 f|=7en, 5
1824 li, 9 hao, 2 miao, 7 hu.'' Here chang,|4.|4.|4.|4,
1833 hu are units of length; 1 hu (the diameter of
1843 a silk thread) equals 1/10 miao, etc. The use
1852 of such decimal-like fractions was fairly widespread
1859 in China after about 1250 {H7}A{H10}.{H7}D{H10}.
1865 The _rst known occurrence of decimal fractions
1872 in a true positional system is in a 10th century
1882 arithmetic text written in Damascus by an obscure
1890 mathematician named al-Uql|=7↓|Zdis|=7↓|Z (``the
1894 Euclidean''). He used the symbol |¬S for a decimal
1903 point, and expressed some fractions and approximate
1910 square and cube roots; but he did not realize
1919 that the integer and fractions parts of numbers
1927 could be multiplied simultaneously. His work
1933 did not become well known, and _ve more centuries
1942 passed before decimal fractions were reinvented
1948 by a Persian mathematician, al-Kash|=7↓|Z, who
1954 died c. 1436. Al-Kash|=7↓|Z was a highly skillful
1962 calculator, who gave the value of 2|ε|≤p |πas
1970 follows, correct to 16 decimal places:|'{A9}|J#>
1977 |∂!!!!|∂!!!!!!!!!!!!!!!!!!!!!!!!|∂|E|;|>integer|;
1980 fractions|;>{B2}|J#>|∂!!|∂!!|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂
1983 !|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂!|9|∂|E|;
1984 |>0|;6|;2|;8|;3|;1|;8|;5|;3|;0|;7|;1|;7|;9|;5|;
2000 8|;6|;5|;>{B2}|J#>This was by far the best approximation
2012 to |ε|≤p |πknown until Ludolph van Ceulen laboriously
2020 calculated 35 decimal places during the period
2027 1596<1610. The earliest known example of decimal
2034 fractions in Europe occurs in a 15th-century
2041 text where, for example, 153.5 is multiplied
2048 by 16.25 to get 2494.375; this was referred to
2057 as a ``Turkish method.'' In 1525, Christof Rudol=
2065 of Germany discovered decimal fractions for himself;
2072 his work never became well-known, either. Fran|=&cois
2079 Vi|=2ete suggested the idea again in 1579. Finally,
2087 an arithmetic text by Simon Stevin of Belgium,
2095 who independently hit on the idea of decimal
2103 fractions in 1585, became popular. His work,
2110 and the discovery of logarithms soon afterwards,
2117 made decimal fractions very common in Europe
2124 during the 17th century. [See D. E. Smith, |εHistory
2133 of Mathematics |≡2 |π(Boston: Ginn and Co., 1925),
2141 228<247, and C. B. Boyer, |εHistory of Mathematics
2149 |π(New York: Wiley, 1968), for further remarks
2156 and references.]|'!|9|7The binary system of notation
2163 has its own interesting history. Many primitive
2170 tribes in existence today are known to use a
2179 binary or ``pair'' system of counting (making
2186 groups of two instead of _ve or ten), but they
2196 do not count in a true radix 2 system, since
2206 they do not treat powers of 2 in a special manner.
2217 See |εThe Di⊃usion of Counting Practices |πby
2224 Abraham Seidenberg, Univ. Calif. Publ. in Math.
2231 |≡3 (1960), 215<300, for interesting details
2237 about primitive number systems. Another ``primitive''
2243 example of an essentially binary system is the
2251 conventional musical notation for expressing
2256 rhythms and durations of time.|'!|9|7Nondecimal
2262 number systems were discussed in Europe during
2269 the seventeenth century. For many years astronomers
2276 had occasionally used sexagesimal arithmetic
2281 both for the integer and the fractional parts
2289 of numbers, primarily when performing multiplication
2295 [see John Wallis, |εTreatise of Algebra |π(Oxford,
2302 1685), 18<22, 30]. The fact that |εany |πpositive
2310 number could serve as radix was apparently _rst
2318 stated in print by Blaise Pascal in |εDe numeris
2327 multiplicibus, |πwhich was written about 1658
2333 [see Pascal's |ε|9Euvres Compl|=2etes |π(Paris:
2338 |=⊂Editions de Seuil, 1963), 84<89]. Pascal woote,
2345 ``Denaria enim ex institute hominum, non ex necessitate
2353 naturae ut vulgus arbitratur, et sane satis inepte,
2361 posita est''; i.e., ``The decimal system has
2368 been established, somewhat foolishly to be sure,
2375 according to man's custom, not from a natural
2383 necessity as most people would think.'' He stated
2391 that the duodecimal (radix twelve) system would
2398 be a welcome change, and he gave a rule for testing
2409 a duodecimal number for divisibility by 9. Erhard
2417 Weigel proposed the quaternary (radix four) system
2424 in a series of publications beginning in 1673.
2432 A detailed discussion of radix twelve arithmetic
2439 was given by Joshua Jordaine, |εDuodecimal Arithmetick
2446 |π(London, 1687).|'!|9|7Although decimal notation
2451 was almost exclusively used for arithmetic during
2458 that era, other systems of weights and measures
2466 were rarely if ever based on multiples of 10,
2475 and many business transactions required a good
2482 deal of skill in adding quantities such as pounds,
2491 shillings, and pence. For centuries merchants
2497 had therefore learned to compute sums and di=erences
2505 of quantities expressed in peculiar units of
2512 currency, weights, and measures; and this was
2519 actually arithmetic in a nondecimal number system.
2526 The common units of liquid measure in England,
2534 dating from the 13th century or earlier, are
2542 particularly noteworthy:|'{A9}|h2 chopins|4|∂α=↓|41
2546 demibushel!!2 demibushels|4|∂α=↓|41 bushel or
2550 _rkin|E|n|;| 2 gills|4|Lα=↓|41 chopin| 2 demibushels|4|Lα=↓|
2554 41 bushel or _rkin>| 2 chopins|4|Lα=↓|41 pint| 2
2561 _rkins|4|Lα=↓|41 kilderkin>| 2 pints|4|Lα=↓|41
2565 quart| 2 kilderkins|4|Lα=↓|41 barrel>| 2 quarts|4|Lα=↓|41
2570 pottle| 2 barrels|4|Lα=↓|41 hogshead>| 2 pottles|4|Lα=↓|41
2575 gallon| 2 hogsheads|4|Lα=↓|41 pipe>| 2 gallons|4|Lα=↓|41
2580 peck| 2 pipes|4|Lα=↓|41 tun>| 2 pecks|4|Lα=↓|41
2585 demibushel>{A9}Quantities of liquid zxpressed
2590 in gallons, pottles, quarts, pints, etc. were
2597 essentially written in binary notation. Perhaps
2603 the true inventors of binary artihmetic were
2610 English wine merchants*3|'!|9|7The _rst known
2616 appearance of binary notation was about 1605
2623 in some unpublished manuscripts of Thomas Harriot
2630 (1560<1621). Harriot was a creative man, who
2637 came to America as a representative of Sir Walter
2646 Raleigh; he invented (among other things) a notation
2654 like that now used for ``less than'' and ``greater
2663 than'' relations; but for some reason he chose
2671 not to publish many of his discoveries. Excerpts
2679 from his notes on binary arithmetic have been
2687 reproduced by John W. Shirley, |εAmer. J. Physics
2695 |≡1|≡9 (1951), 452<454. |πThe _rst published
2701 discussion of the binary system was given in
2709 a comparatively little-known work by a Spanish
2716 bishop, Juan Caramuel Lobkowitz, |εMathesis biceps
2722 |≡1 |π(Campaniae, 1670), 45<48; Caramuel discussed
2728 the representation of numbers in radices 2, 3,
2736 4, 5, 6, 7, 8, 9, 10, 12, and 60 at some length,
2749 but gave no examples of arithmetic operations
2756 in nondecimal systems (except for the trivial
2763 operation of adding unity).|'|Hβ*?*?*?*?{U0}{H10L12M29}|π58320#C
folio 241 galley 3
2767 omputer Programming!(Knuth/Addison-Wesley)!f.
2769 241!ch. 4!g. 3|'{A6}!|9|7Ultimately, an article
2775 by G. W. Leibnitz |ε[Memoires de l'Academie Royale
2783 des Sciences |π(Paris, 1703), 110<116], which
2789 illustrated binary addition, subtraction, multiplication,
2794 and division, really brought binary notation
2800 into the limelight, and this article is usually
2808 referred to as the birth of radix 2 arithmetic.
2817 Leibnitz later referred to the binary system
2824 quite frequently [cf. W. Ahrens, |εMathematische
2830 Unterhaltungen und Spiele |≡1 |π(Leipzig: Teubner,
2836 1910), 27<28]. He did not recommend it for practical
2845 calculations, but he stressed its importance
2851 in number-theoretical investigations, since patterns
2856 in number sequences are often more apparent in
2864 binary notation than they are in decimal; he
2872 also saw a mystical signi_cance in the fact that
2881 everything is expressible in terms of zero and
2889 one [see Laplace, |εTh|=1eorie Analytique des
2895 Probabilit|=1es, |π3rd ed. (Paris, 1820), cix].|'
2901 !|9|7It is interesting to note that the important
2909 concept of negative powers to the right of the
2918 radix point was not yet well understood at that
2927 time. Leibnitz asked James Bernoulli to calculate
2934 |ε|≤p |πin the binary system, and Bernoulli ``solved''
2942 the problem by taking a 35-digit approximation
2949 to |ε|≤p, |πmultiplying it by 10|g3|g5, and then
2957 expressing this integer in the binary system
2964 as his answer. On a smaller scale this would
2973 be like saying that |ε|≤p|4|¬V|43.14, |πand (314)|β1|β0|4α=↓
2979 |4(100111010)|β2; hence |ε|≤p |πin binary is
2985 100111010*3 [See Leibnitz, |εMath. Schriften |π(ed.
2991 Gehrhardt), |≡3 (Halle: 1855), 97; two of the
2999 118 bits in the answer are incorrect, due to
3008 computational errors.] The motive for Bernoulli's
3014 calculation was apparently to see whether any
3021 simple pattern could be observed in this representation
3029 of |ε|≤p.|'|π!|9|6Charles XII of Sweden, whose
3036 talent for mathematics perhaps exceeded that
3042 of all other kings in the history of the world,
3052 hit on the idea of radix-8 srithmetic about 1717.
3061 This was probably his own invention, although
3068 he had met Leibnitz brie⊗y in 1707. Charles felt
3077 radix 8 or 64 would be more convenient for calculation
3087 than the decimal system, and he considered introducing
3095 octal arithmetic into Sweden; but he died in
3103 battle before carrying out such a change. [See
3111 |εThe Works of Voltaire |≡2|≡1 |π(Paris: E. R.
3119 DuMont, 1901), 49; E. Swedenborg, |εGentleman's
3125 Magazine |≡2|≡4 (1754), 423<424.]|'!|9|7|πOctal
3130 notation was proposed also in colonial America
3137 before 1750, by the Rev. Hugh Jones, rector of
3146 a parish in Maryland (cf. |εGentleman's Magazine
3153 |≡1|≡5 |π(1745), 377<379; H. R. Phalen, |εAMM
3160 |≡5|≡6 (1949), 361<465).|'|π!|9|7More than a
3166 century later, a prominent Swedisym-A*?|π!|9|7More
3171 than a century later, a prominent Swedish-American
3178 civil engineer named John W. Nystrom decided
3185 to carry Charles XII's plans a step further,
3193 by devising a complete system of numeration,
3200 weights, and measures based on hexadecimal (radix
3207 16) arithmetic. He wrote, ``I am not afraid,
3215 or do hot hesitate, to advocate a binary system
3224 of arithmetic and metrology. I know I have nature
3233 on my side; if I do not succeed to impress upon
3244 you its utility and great importance to mankind,
3252 it will re⊗ect that much less credit upon our
3261 generation, upon our scienti_c men and philosophers.''
3268 Nystrom devised special means for pronouncing
3274 hexadecimal numbers; e.g. |≤#|¬b|¬0|¬1|¬6|¬0|≤&|β1|β6
3278 was to be read ``vybong, bysanton.'' His entire
3286 system was called the Tonal System, and it is
3295 described in |εJ. Franklin Inst. |≡4|≡6 (1863),
3302 263<275, 337<348, 402<407. |πA similar system,
3308 but using radix 8, was worked out by Alfred B.
3318 Taylor |ε[Proc. Amer. Pharmaceutical Assoc. |≡8
3324 (1859), 115<216; Proc. Amer. Philosophical Soc.
3330 |≡2|≡4 (1887), 296<366]. |πIncreased use of the
3337 French (metric) system of weights and measures
3344 prompted extensive debate about the merits of
3351 decimal arithmetic during that era; indeed, octal
3358 arithmetic was even being proposed in France
3365 [Aim|=1e Mariage, |εNum|=1eration par huit |π(Pars:
3371 Le Nonnant, 1857)].|'!|9|7The binary system was
3378 well-known as a curiosity ever since Leibnitz's
3385 time, and ab out 20 early references to it have
3395 been compiled by R. C. Archibald [|εAMM |≡2|≡5
3403 (1918), 139<142]. |πIt was applied chie⊗y to
3410 the calculation of powers, as explained in Section
3418 4.6.3, and to the analysis of certain games and
3427 puzzles. G. Peano |ε[Atti della R. Accademia
3434 delle Scienze di Torino |≡3|≡4 (1898), 47<55]
3441 |πused binary notation as the basis of a ``logical''
3450 character set of 256 symbols. Joseph Bowden |ε[Special
3458 Topics in Theoretical Arithmetic |π(Garden City:
3464 1936), 49] gave his own system of nomenclature
3472 for hexadecimal numbers.|'!|9|7The book |εHistory
3478 of Binary and Other Nondecimal Numeration |πby
3485 Anton Glaser (privately printed, 1971) contains
3491 an informative and nearly complete discussion
3497 of the development of binary notation, including
3504 English translations of amny of the works cited
3512 above.|'!|9|7Increased interest in mechanical
3517 devices for doing arithmetic, especially for
3523 multiplication, led several people to consider
3529 the binary system for this purpose. A particularly
3537 delightful account of this activity appears in
3544 the article ``Binary Calculation'' by E. William
3551 Phillips |ε[Journal of the Institute of Actuaries
3558 |≡6|≡7 (1936), 187<221] |πtogether with a record
3565 of the discussion which followed a lecture he
3573 gave on the subject. Phillips began by saying,
3581 ``The ultimate aim [of this paper] is to persuade
3590 the whole civilized world to abandon decimal
3597 numeration and to use octonal [ilel, radix 8]
3605 numeration in its place.''|'!|9|7Modern readers
3611 of Phillips's article will perhaps be surprised
3618 to discover that a radix-8 number system was
3626 properly referred to as ``octonary'' or ``octonal,''
3633 according to all dictionaries of the English
3640 language at that time, just as the radix-10 number
3649 system is properly called either ``denary'' or
3656 ``decimal''; the word ``octal'' did not appear
3663 in English language dictionaries until 1961,
3669 and it apparently originated as a term for the
3678 ``base'' of a certain class of vacuum tubes.
3686 The wordd ``hexadecimal,'' which has crept into
3693 our languate even more recently, is a mixture
3701 of Greek and Latin stems; more proper terms would
3710 be ``senidenary'' or ``sedecimal'' or even ``sexacecimal,''
3717 but the latter is perhaps too risqu|=1e for computer
3726 programmers.|'!|9|7The comment by Mr. Wales which
3733 is quited at the beginning of this chapter has
3742 been taken from the discussion printed with Mr.
3750 Phillips's paper. Another man who attended the
3757 same lecture objected to the octal system for
3765 business purposes: ``5% becomes 3.1463 per 64,
3772 which sounds rather horrible.''|'!|9|7Phillips
3777 got the inspiration for his proposals from an
3785 electronic circuit which was capable of counting
3792 in binary [C. E. Wyn-Williams, Proc. Roy. Soc.
3800 London |≡A|≡1|≡3|≡6 (1932), 312<324]. Electromechanical
3805 and electronic circuitry for general arithmetic
3811 operations was developed during the late 1930's,
3818 notably by John V. Atanaso= and George R. Stibitz
3827 in the U.S.A., L. Cou∃gnal and R. Valtat in France,
3837 Helmut Schreyer and Konrad Zuse in Germany. All
3845 of these inventors used the binary system, although
3853 Stibitz later developed excess-3 binary-coded-decimal
3858 notation. A fascinating account of these early
3865 developments, including reprints and translations
3870 of important acontemporary documents, appears
3875 in Brian Randell's book |εThe Origins of Digital
3883 Computers |π(Berlin: Springer, 1973).|'!|9|7The
3888 _rst American high-speed computers, built in
3894 the early 1940's, used decimal arithmetic. But
3901 in 1946, an important memorandum by A. W. Burks,
3910 H. H. Goldstine, and J. von Neumann, in connection
3919 with the design of the _rst stored-program computers,
3927 gave detailed reasons for the deacision to make
3935 a radical departure from tradition and to use
3943 base-two notation [see John von Neumann, |εCollected
3950 Works |≡5|≡, 41<65]. |πSince then binary computers
3957 have beacome commonplace. After a dozen years
3964 of experience with binary machines, a discussion
3971 of the relative advantages and disadvantages
3977 of binary notation was given by W. Buchholz in
3986 his paper ``Fingers or Fists?'' |ε[CACM |≡2 |π(December,
3994 1959), 3<11].|'!|9|7The |¬m|¬i|¬x computer used
4000 in this book has been de_ned so that it can be
4011 either binary or decimal. It is interesting to
4019 note that nearly all |¬m|¬i|¬x programs can be
4027 expressed without knowing whether binary or decimal
4034 notation is being used#even when we are doing
4042 calculations involving multiple-precision arithmetic.
4046 Thus we _nd that the choice of radix does not
4056 signi_cantly in⊗uence computer programming. (Noteworthy
4061 exceptions to this statement, however, are the
4068 ``Boolean'' algorithms discussed in Section 7.1;
4074 see also Algorithm 4.5.2B.)|'!|9|7There are several
4081 di=erent methods for representing |εnegative
4086 |πnumbers in a computer, and this sometimes in⊗uences
4094 the way arithmetic is done. In order to understand
4103 these other notations, let us _rst consider |¬m|¬i|¬x
4111 as if it were a decimal computer; then each word
4121 contains 10 digits and a sign, e.e.,|'{A8}|→α_↓12345|467890.
4128 |J!(2)|;{A9}This is called the |εsigned-magnitude
4134 |πrepresentation. Such a representation corresponds
4139 to common notational conventilns, so it is preferred
4147 by many programmers. A otential disadvantage
4153 is that minus zero and plus zero can both be
4163 represented, while they usually should mean the
4170 same number; this possibility requires some care
4177 in practive.|'!|9|7Most mechanical calculators
4182 that do decimal arithmetic use another system
4189 called |εten's complement |πnotation. If we subtract
4196 1 from 00000|400000, we get 99999|499999 in this
4204 notation; in other wods, no explicit sign is
4212 attached to the number, and calculation is |εdone
4220 modulo 10|g1|g0. |πThe number |→α_↓12345|467890
4225 would appear as|'{A8}87654|432110|J!(3)|;{A9}in
4230 ten's complement notation. It is conventional
4236 to regard any number whose leading digit is 5,
4245 6, 7, 8, or 9 as a negative value in this notation,
4257 although with respect to addition and subtraction
4264 there is no harm in regarding (3) as the number
4274 |→α+↓87654|432110 if it is conveneint to do so.
4282 There is no problem of ``minus zero'' with ten's
4291 complement notation. The major di=erence between
4297 signed magnitude and ten's complement notation.
4303 The major di=erence between signed magnitude
4309 and ten's complement notations in practice is
4316 that shigting right does not divide the magnitude
4324 by ten; for example, the number |→α_↓11|4α=↓|4.|4.|4.|4.|499
4330 989, shifted right one, gives .|4.|4.|499998|4α=↓|4|→α_↓2
4336 |π(assuming that a shift to the right inserts
4344 ``9'' as the leading digit when the number shifted
4353 is negative). In general, |εx |πshifted right
4360 one digit in ten's complement notation will give
4368 |"l|εx/10|"L, |πwhether |εx |πis positive or
4374 negative. A possible disadvantage of the ten's
4381 complement system is the fact that it is not
4390 symmetric about zero; the largest negative number
4397 representable in |ε{U0}{H10L12M29}|π58320#Computer
folio 245 galley 4
4400 Programming!(Knuth/Addison-Wesley)!f. 245!ch.
4402 4!g. 4|'{A6}!|9|7Another notation which has been
4409 used since the earliest days of high-speed computers
4417 is called |εnines' complement |πrepresentation.
4422 In this case the number |→α_↓12345|467890 would
4429 appear as|'{A9}87654||432109.|J!(4)|;{A9}Each
4433 digit of a negative number |ε|→α_↓x |πis equal
4441 to 9 minus the corresponding digit of |εx. |πIt
4450 is not di∃cult to see that the nines' complement
4459 notation for a negative number is always one
4467 less than the corresponding ten's complement
4473 notation; addition and subtraction are done modulo
4480 10|g1|g0|4α_↓|41, which means that a carry o=
4487 the left end is to be added at the right end.
4498 (Cf. Section 3.2.1.1) Again there is a potential
4506 problem with minus zero, since 99999|499999 and
4513 00000|400000 denote the same value.|'!|9|7The
4519 ideas just explained for base-10 arithmetic apply
4526 in a similar way to base-2 arithmetic, where
4534 we have |εsigned magnitude, two's complement,
4540 |πand |εones' complement |πnotations. The |¬m|¬i|¬x
4546 computer, as used in the examples of this chapter,
4555 deals only with signed-magnitude arithmetic:
4560 alternative procedures for complement notations
4565 are discussed in the accompanying text when it
4573 is important to do so.|'!|9|7Most computer manuals
4581 tell us that the machine's circuitry assumes
4588 that the radix point is situated in a particular
4597 place within each computer word. This advice
4604 should usually be disregarded; it is better to
4612 learn the rules concerning where the radix point
4620 will appear in the result of an instruction if
4629 we assume that it lies in a certain place beforehand.
4639 For example, in the case of |¬m|¬i|¬x we could
4648 regard our operands either as integers with the
4656 radix point at the extreme right, or as fractions
4665 with the radix point at the extreme left, or
4674 as some mixture of these two extremes; the rules
4683 for the appearance of the radix point in each
4692 result are straightforward.|'!|9|7It is easy
4698 to see that there is a simple relation between
4707 radix |εb |πand radix |εb|gk:|'{A9}(.|4.|4.|4a|β3a|β2a|β1a|β
4712 0.a|βα_↓|β1a|βα_↓|β2|4.|4.|4.)|βb|4α=↓|4(.|4.|4.|4A|β3A|β2A|
4712 β1A|β0.A|βα_↓|β1A|βα_↓|β2|4.|4.|4.)|βb|lk,|J!(5)|;
4713 |πwhere|'|εA|βj|4α=↓|4(a|βk|βj|βα+↓|βk|βα_↓|β1|4.|4.|4.|4a|β
4714 k|βj|βα+↓|β1a|βk|βj)|βb;|;{A9}|πsee exercise
4717 8. Thus we obtain the simple techniques for converting
4726 at sight between, say, binary and octal notation.|'
4734 !|9|7There are many interesting variations on
4740 positional number systems besides the standard
4746 |εb-|πary systems discussed so far. For example,
4753 we might have numbers in base (|→α_↓10), so that|'
4762 {A9}|ε(.|4.|4.|4a|β3a|β2a|β1a|β0.a|βα_↓|β1a|βα_↓|β2|4.|4.|4.
4762 )|βα_↓|β1|β0|'{A12}|∂α=↓|4|¬O|4|¬O|4|¬O|4α_↓|4100a|β3|4α+↓|4
4763 100a|β2|4α_↓|410a|β1|4α+↓|4a|β0|4α_↓|4|f1|d310|)a|βα_↓|β1|4α
4763 +↓|4|f1|d3100|)a|βα_↓|β2|4α_↓|4|¬O|4|¬O|4|¬O|4.|E|?
4764 {B12}|Lα=↓|4|¬O|4|¬O|4|¬O|4α+↓|4a|β3(|→α_↓10)|g3|4α+↓|4a|β2(
4764 |→α_↓10)|g2|4α+↓|4a|β1(|→α_↓10)|g1|4α+↓|4a|β0|4α+↓|4|¬O|4|¬O
4764 |4|¬O>{A12}{A9}|πHere the individual digits satisfy
4770 0|4|¬E|4|εa|βk|4|¬E|49 |πjust as in the decimal
4776 system. The number 12345|467890 would appear
4782 in the ``negadecimal'' system as|'{A9}(1|493755|473910)|βα_↓
4787 |β1|β0,|J!(6)|;{A9}since the latter represents
4792 10305070900|4α_↓|49070503010. It is interesting
4796 to note that the negative of this number, |→α_↓12345|467890,
4804 would be written|'{A9}(28466|448290)|βα_↓|β1|β0,|J!(7)|;
4809 {A9}and, in fact, |εevery real number whether
4816 positive or negative can be represented without
4823 a sign |πin the |→α_↓10 system.|'!|9|7Negative-base
4830 systems were _rst considered by Vittorio Gr|=4unwald
4837 |ε[Giornale di matematiche di Battaglini |≡2|≡3
4843 (1885), 203<221, 367], |πwho explained how to
4850 perform the four arithmetic operations in such
4857 systems; he also discussed root extraction, divisibility
4864 tests, and rdadix conversion. However, since
4870 his work was published in such an obscure journal,
4879 it seems to have had no e=ect on other research,
4889 and it was soon forgotten. The next mention of
4898 negative-base systems in literature was apparently
4904 by A. J. Kempner |ε[AMM |≡4|≡3 (1936), 610<617],
4912 |πwho discussed the properties of non-integer
4918 radices and remarked in a footnote that negative
4926 radices would be feasible too. After twenry more
4934 years the idea was rediscovered again, this time
4942 by Z. Pawlak and A. Wakulicz |ε[Bulletin de l'Academie
4951 Polonaise des Sciences, |πClasse III, |≡5 (1957),
4958 233<236; S|=1erie des sciences techniques |≡7
4964 (1959), 713<721], and by L. Wadel [|εIRE Transactions
4972 |π|≡E|≡C|≡-|≡6 (1957), 123]. For further references
4978 see IEEE |εTransactions |π|≡E|≡C|≡-|≡1|≡2 (1963),
4983 274<276; |εComputer Design |≡6 |π(May, 1967),
4989 52<63. (There is evidence that the idea of negative
4998 bases occurred independently to quite a few people.
5006 For example, D. E. Knuth had discussed negative-base
5014 systems in 1955 in a short paper submitted to
5023 a ``science talent search'' contest for high-school
5030 seniore, together with a further generalization
5036 to complex-valued bases.)|'!|9|7The base 2|εi
5042 |πgives an interesting system called the ``quater-imaginary'
5048 ' number system (by analogy with ``quaternary'')
5055 since |εevery complex number canf be represented
5062 with the digits |*/0, 1, 2, |\and |*/3|\ without
5071 a sign |πin this system. [See |εCACM |≡3 (1960),
5080 245<247.] |πFor example,|'{A9}|ε(11210.31)|β2|βi|4|∂α=↓|41|4
5083 |¬O|416|4α+↓|41|4|¬O|4(|→α_↓8i)|4α+↓|42|4|¬O|4(|→α_↓4)|4α+↓|
5083 41|4|¬O|4(2i)|4α+↓|43|4|¬O|4(|→α_↓|f1|d32|)i)|4α+↓|41(|→α_↓|
5083 f1|d34|))|;{A4}|Lα=↓|47|f3|d34|)|4α_↓|47|f1|d32|)i.>
5085 {A9}|πHere the number |ε(a|β2|βn|4.|4.|4.|4a|β1a|β0.a|βα_↓|β
5088 1|4.|4.|4.|4a|βα_↓|β2|βk)2|βi |πis equal to|'
5092 {A9}|ε(a|β2|βn|4.|4.|4.|4a|β2a|β0.a|βα_↓|β2|4.|4.|4.|4a|βα_↓
5092 |β2|βk)|βα_↓|β4|4α+↓|42i(a|β2|βn|βα_↓|β1|4.|4.|4.|4a|β3a|β1.
5092 a|βα_↓|β1|4.|4.|4.|4a|βα_↓|β2|βk|βα+↓|β1)|βα_↓|β4,|;
5093 {A9}|πso conversion to and from quater-imaginary
5099 notation reduces to conversion to and from negative
5107 quaternary representation of the real and imaginary
5114 parts. The interesting property of this system
5121 is that it allows multiplication and division
5128 of complex numbers to be done in a fairly uni_ed
5138 manner without treating real and imaginary parts
5145 separately. For example, we can multiply two
5152 numbers in this system much as we do with any
5162 base, merely using a di=erent ``carry'' rule:
5169 whenever a digit exceeds 4 we subtract 4 and
5178 ``carry'' a |→α_↓1 two columns to the left; when
5187 a digit is negative, we add four to it and ``carry''
5198 |→α+↓1 two columns to the left. A study of the
5208 following example shows this peculiar carry rule
5215 at work:|'{A9}|h|∂0|42|41|42|42|42|42|42|42!!|∂[|→α_↓19|4α_↓
5217 |4180i]|E|n|;|L!!!|21|42|42|43|41|L[9|4α_↓|4|ε10i]>
5219 |L!!!|21|42|42|43|41|L[9|4α_↓|410i]>{B2}|L!!!|2####>
5221 |L!!!|21|42|42|43|41>|L1|40|43|42|40|42|41|43>
5223 |L!|9|11|43|40|42|42>|L|9|51|43|40|42|42>|L1|42|42|43|41>
5226 {B2}|L#######>|L0|42|41|43|43|43|41|42|41|L[|→α_↓19|4α_↓|418
5227 0i]>{A9}|π!|9|7A similar system which uses just
5234 the digits 0 and 1 may be based on {H11}|¬H{H10}|v42|)|εi,
5244 |πbut this requires an in_nite nonrepeating expansion
5251 for the simple number ``|εi'' |πitself.|'!|9|7A
5258 ``binary'' complex number system may also be
5265 obtained by using the base |εi|4α_↓|41, |πas
5272 suggested by W. Penney [|εJACM |≡1|≡2 (1965),
5279 247<248]:|'{A9}(.|4.|4.|4a|β4a|β3a|β2a|β1a|β0.a|βα_↓|β1|4.|4
5280 .|4.)|βi|βα_↓|β1|'α=↓|4|¬O|4|¬O|4|¬O|4|→α_↓4a|β4|4α+↓|4(2|4α
5281 +↓|42i)a|β3|4α_↓|42ia|β2|4α+↓|4(i|4α_↓|41)a|β1|4α+↓|4a|β0|4α
5281 _↓|4|f1|d32|)(i|4α+↓|41)a|βα_↓|β1|4α+↓|4|¬O|4|¬O|4|¬O|4.|?
5282 {A9}|π!|9|7In this system, only the digits 0
5289 and 1 are needed. One way to whow that every
5299 complex number has such a representation is to
5307 consider the interesting set |εS |πshown in Fig.
5315 1; this set is, by de_nition, all points which
5324 can be written as |ε|¬K|ur|)k|¬R1|)|4a|βk(i|4α_↓|41)|gα_↓|gk
5328 , |πfor an in_nite sequence |εa|β1, a|β2, a|β3,
5336 . . . |πof zeros and ones. Figure 1 shows how
5347 |εS |πcan be decomposed into 256 pieces congruent
5355 to |f1|d316|)|εS; |πnote that if the diagram
5362 of |εS |πis rotated counterclockwise by 135|¬P,
5369 we obtain two adjacent sets congruent to (1/{H11}|¬H{H10}|v4
5376 2|))|εS |π(since |ε(i|4α_↓|41)S|4α=↓|4S|4|↔q|4(S|4α+↓|41){H1
5378 2}){H10}. |πFor details of a proof that |εS |πcontains
5387 all complex numbers that are of su∃ciently small
5395 magnitude, see exercise 18. (Actually, the boundary
5402 of |εS |πcontains many jagged edges; these corners
5410 have been rounded o= in Figure 1.)|'|Hβ*?*?*?{U0}{H10L12M29}|π5
folio 249 galley 5
5417 8320#Computer Programming!(Knuth/Addison-Wesley)!f.
5419 249!ch. 4!g. 5|'{A6}{H9L11}|≡F|≡i|≡g|≡. |≡1|≡.|9|4The
5424 set |εS. |π(Illustration by P. M. Farmwald, R.
5432 W. Gosper, and R. E. Mass.)|;{A7}{H10L12}!|9|7Perhaps
5439 the prettiest number system of all is the |εbalanced
5448 ternary |πnotation, which consists of base 3
5455 representation using the ``trits'' |→α_↓1, 0,
5461 |→α+↓1 instead of 0, 1, and 2. If we use the
5472 symbol |=∩1 to stand for |→α_↓1, we have the
5481 following examples of balanced ternary numbers:|'
5487 {A9}|∂!!!!!!!!|6|∂!!!|∂!!!|9|2|∂|E|;|>Balanced
5490 ternary|;|;Decimal|;>{A3}|>|9|51|40|4|=∩1|'|;
5497 |9|2!|4|48|'>|>1|41|4|=∩1|40.|=∩1|4|=∩1|'|;|9|2|9|732|f5|d39
5502 |)|;>|>|=∩1|4|=∩1|41|40.1|41|'|;|9|2|→α_↓32|f5|d39|)|'
5508 >|>|=∩1|4|=∩1|41|40|'|;|9|2|→α_↓33|'>|>!!|60.1|41|41|41|41|4
5515 .|4.|4.|'|;|9|2|9|7!|2|f1|d32|)|'>{A9}!|9|7The
5520 balanced ternary number system has many pleasat
5527 properties:|'{A4}{I2.9H}!|9|7a)|9|1The negative
5530 of a number is obtained by interchanging 1 and
5539 |=∩1.|'!|9|7b)|9The sign of a number is given
5547 by its most signi_cant nonzero ``trit,'' and
5554 more generally we can compare any two numbers
5562 by reading them from left to right and using
5571 lexicographic order, as in the decimal system.|'
5578 !|9|7c)|9|2The operation of rounding to the nearest
5585 integer is identical to truncation (i.e., deleting
5592 everything to the right of the decimal point).|'
5600 {A6}{IC}Addition in the balanced ternary system
5606 is quite simple, using the table|'{A9}|9|1|=∩1|9|9|1|=∩1|9|=
5612 ∩1|9|2|9|1|=∩1|9|=∩1|9|2|=∩1|9|2|=∩1|9|2|=∩1|9|2|=∩1|9|2|9|1
5612 0|9|10|9|20|9|20|9|20|9|20|9|20|9|20|9|2|9|10|9|11|9|21|9|21
5612 |9|21|9|21|9|21|9|11|9|2|9|11|9|1|9|11|'|9|1|=∩1|9|9|1|=∩1|9
5613 |=∩1|9|9|30|90|9|20|9|21|9|21|9|21!|3|=∩1|9|1|=∩1|9|2|=∩1|9|
5613 20|9|20|9|20|9|21|9|21!|31|9|1|=∩1|9|2|=∩1|9|2|=∩1|9|20|9|20
5613 |9|2|9|10|9|11|9|2|9|11!|21|'|9|1|=∩1!|10|91!|3|=∩1|90|9|21|
5614 9|2|=∩1|9|20|9|21!|3|=∩1|9|10|9|21|9|2|=∩1|9|20|9|21|9|2|=∩1
5614 |9|20!|31|9|1|=∩1|9|20|9|21|9|2|=∩1|9|20!|31|9|1|=∩1!|30!|21
5614 |'{B2}|J#>|=∩10|9|=∩11|9|=∩1|9|2|=∩11|9|=∩1|9|20|9|2|=∩1|9|2
5616 0|9|21|9|2|=∩11|9|1|=∩1|9|20|9|2|=∩1|9|20|9|21|9|20|9|21|9|2
5616 1|=∩1|9|1|=∩1|9|20|9|21|9|20|9|21|9|21|=∩1|9|11|9|21|=∩1|9|1
5616 10|'{A9}(The three inputs to the addition are
5624 the digits of the numbers to be added and the
5634 carry digits.) Subtraction is negation followed
5640 by addition; and multiplicationalso reduces to
5646 negation and addition, as in the following example:|'
5654 {A9}|∂!!|61|4|=∩1|40|4|=∩1!!|∂[17]|;|L!!|61|4|=∩1|40|4|=∩1|L
5655 [17]>{B2}|L!!|6###>|L!!|6|=∩1|41|40|41>|L|9|5|=∩1|41|40|41|4
5658 0>|L1|4|=∩1|40|4|=∩1>{B2}|L#####>|L0|41|41|4|=∩1|4|=∩1|40|41
5661 |L[289]>{A9}For division, see exercise 4.3.1<31.|'
5667 !|9|7One way to _nd the representation of a number
5676 in the balanced ternary system is to start by
5685 representing it in the ternary notation; for
5692 example,|'{A9}208.3|4α=↓|4(21201.022002200220|4.|4.|4.)|β3.|
5693 ;{A9}(A very simple pencil-and-paper method for
5700 converting to ternary notation is given in exercise
5708 4.4<12.) Now add the in_nite number .|4.|4.|411111.11111|4.|
5714 4.|4. in ternary notation; we obtain, in the
5722 above example,|'{A9}(.|4.|4.|411111210012.210121012101|4.|4.
5724 |4.)|β3.|;{A9}Finally, subtract .|4.|4.|411111.11111|4.|4.|4
5727 . by decrementing each digit; we get|'{A6}208.3|4α=↓|4(10|v4
5734 11|)01.10|=∩1010|=∩1010|=∩10|4.|4.|4.)|β3.|J!(8)|;
5735 {A9}This process may clearly be made rigorous
5742 if we replace the arti_cial in_nite number .|4.|4.|411111.11
5749 111|4.|4.|4. by a number with suitably many ones.|'
5757 !|9|7Representation of numbers in the balanced
5763 ternary system is implicitly present in a famous
5771 mathematical puzzle, which is commonly called
5777 ``Bachet's problem of weights,'' although it
5783 was already stated by Fibonacci four centuries
5790 before Bachet wrote his book. [See W. Ahrens,
5798 |εMathematische Unterhaltungen und Spiele |≡1
5803 |π(Leipzig: Teubner, 1910), Sir John Leslie [|εThe
5810 Philosophy of Arithmetic |π(Edinburgh, 1817);
5815 see pp. 33<34, J. Colson |ε[Philos. Trans. |≡3|≡4
5823 (1726), 161<173], |πand independently by Sir
5829 John Leslie |ε[The Philosophy of Arithmetic |π(Edinburgh,
5836 1817); see pp. 33<34, 54, 64<65, 117, 150], and
5845 independently by A. Cauchy |ε[Comptes Rendus
5851 |≡1|≡1 |π(Paris, 1840), 789<798], who pointed
5857 out that negative digits make it unnecessary
5864 for a person to memorize the multiplication table
5872 past 5|4α⊗↓|45. The _rst true appearance of ``pure''
5880 balanced ternary notation was in an article by
5888 L|=1eon Lalanne |ε[Comptes Rendus |≡1|≡1 |π(Paris,
5894 1840), 903<905], who was a designer of mechanical
5902 devices for arithmetic. The system was mentioned
5909 only rarely for 100 years after Lalanne's paper,
5917 until the development of the _rst electronic
5924 computers at the Moore School of Electrical Engineering
5932 in 1945<1946; at that time it was given serious
5941 consideration along with the binary system as
5948 a possible replacement for the decimal system.
5955 The complexity of arithmetic circuitry for balanced
5962 ternary arithmetic is not much greater than it
5970 is for the binary system, and a given number
5979 requires only ln|42/ln|43|4|¬V|463% as many digit
5985 positions for its representation. Discussionf
5990 of the balanced ternary number system appear
5997 in |εAMM |≡5|≡7 (1950), 90<93; |πand in |εHigh-speed
6005 Computing Devices, |πEngineering Research Associates
6010 (McGraw-Hill, 1950), 287<289. The experimental
6015 Russian computer |¬s|¬e|¬t|¬u|¬n was based on
6021 balanced ternary notation [see |εCACM |≡3 (1960),
6028 149<150], |πand perhaps the symmetric properties
6034 and simple arithmetic of this number system will
6042 prove to be quite important some day (when the
6051 ``⊗ip-⊗op'' is replaced by a ``⊗ip-⊗ap-⊗op'').|'
6057 !|9|7Another important generalization of the
6062 simple positional notation is a |εmixed radix
6069 |πsystem. If we have a sequence of numbers |↔b|εb|βk|↔v
6078 |π(where |εk |πmay be negative), we de_ne|'{A9}|ε|↔d|(.|4.|4
6085 .|4,|4a|β3,|5a|β2,|5a|β1,|5a|β0;|9|1a|βα_↓|β1.|5a|βα_↓|β2,|5
6085 .|4.|4.|d5.|4.|4.|4,|4b|β3,|4b|β2,|4b|β1,|4b|β0;|9b|βα_↓|β1,
6085 |4b|βα_↓|β2,|4.|4.|4.|)|↔f|;{A4}α=↓|4|¬O|4|¬O|4|¬O|4α+↓|4a|β
6086 3b|β2b|β1b|β0|4αt↓|4a|β2b|β1b|β0|4α+↓|4a|β1b|β0|4α+↓|4a|β0|4
6086 α+↓|4a|βα_↓|β1/b|βα_↓|β1|4α+↓|4a|βα_↓|β2/b|βα_↓|β1b|βα_↓|β2|
6086 4α+↓|4|¬O|4|¬O|4|¬O|4.|;(9)|?{A9}|πIn the simplest
6091 mixed-radix systems, we work only with integers;
6098 we let |εb|β0, b|β1, b|β2,|4.|4.|4. |πbe integers
6105 greater than one, and deal only with numbers
6113 that have no radix point, where |εa|βk |πis required
6122 to lie in the range 0|4|¬E|4|εa|βk|4|¬W|4b|βk.|'
6128 |π!|9|7One of the most important mixed radix
6135 systems is the |εfactorial number system, |πwhere
6142 |εb|βk|4α=↓|4k|4α+↓|42. |πUsing this system,
6146 we can represent every positive integer uniquely
6153 in the form|'{A9}|εc|βnn*3|4α+↓|4c|βn|βα_↓|β1(n|4α_↓|41)*3|4α+
6156 ↓|4|¬O|4|¬O|4|¬O|4α+↓|4c|β22*3|4α+↓|4c|β1|J!(10)|;
6157 {A9}|πwhere |ε0|4|¬E|4c|βk|4|¬E|4k, |πand |εc|βn|4|=|↔6α=↓|4
6160 0. |π(See Algorithm 3.32P.)|'!|9|7Mixed-radix
6165 systems are familiar in everyday life, when we
6173 deal with units of measure. For example, the
6181 quantity ``3 weeks, 2 days, 9 hours, 22 minutes,
6190 57 seconds, and 492 milliseconds'' is equal to|'
6198 {A9}|↔d|(3,|42,|4|9|19,|422,|457;|9|9|1492|d5|9|1|97,|424,|4
6198 60,|460;|91000|)|↔f|4seconds.|;{A9}The quantity
6201 ``10 pounds, 6 shillings, and trhuppence ha'penny''
6208 was once [|f10,|d55|)|4|f|9|16,|d520,|)|4|f|9|13;|d512;|)|4|
6210 f1|d52|)] pence in English currency, before England
6217 changed to a pure decimal monettary system.|'
6224 !|9|7It is possible to add and subtract mixed
6232 radix numbers by using a straightforward generalization
6239 of the usual addition and subtraction algorithms,
6246 provided of course that the same mixed radix
6254 system is being used for both operands (see exercise
6263 4.3.1<9). Similarly, we can easily multiply or
6270 divide a mixed-radix number by small integer
6277 constants, using simple extensions of the familiar
6284 pencil-and-paper methods.|'!|9|7Mixed-radix systems
6288 were _rst discussed generally by Georg Cantor
6295 |ε[Zeitschrift f|=4ur Mathematik und Physik |≡1|≡4
6301 (1869), 121<128]. |πFor further information about
6307 mixed-radix system, see exercises 26 and 29.|'
6314 !|9|7Besides the systems described in this section,
6321 there are several other ways to represent numbers,
6329 which are mentioned elsewhere in this series:
6336 the binomial number system (exercise 1.2.6<56);
6342 the Fibonacci number system (exercise 1.2.8<34);
6348 the phi number system (exercise 1.2.8<35); modular
6355 representations (Section 4.3.2); Gray code (Section
6361 7.2.1); and roman numerals (Section 9.1).|'!|9|7Some
6368 questions concerning |εirrational |πradices have
6373 been investigated by W. Parry, |εActa Mathematica,
6380 |πAcad. Sci. Hung., |≡1|≡1 (1960), 401<416.|'
6386 {A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A11}{H9L11}|9|1|≡1|≡.|9|4
6387 [|*/|↔O|↔C|\] Express the numbers |→α_↓10, |→α_↓9,|4.|4.|4.|4
6392 , 9, 10 in the base |→α_↓2 number system.|'{A3}|9|1|≡2|≡.|9|
6401 4[|*/|↔P|↔M|\] Consider the following four number
6407 systems: (a) binary (signed magnitude); (b) negative
6414 binary (radix |→α_↓2); (c) balanced ternary;
6420 and (d) radix |εb|4α=↓|4|f1|d310|). |πUse each
6426 of these number systems to express each of the
6435 following three numbers: (i) |→α_↓49; (ii) |→α_↓3|f1|d37|)
6442 (show the repeating cycle); (iii) |ε|≤p |π(to
6449 a few signi_cant _gures).|'{A3}|9|1|≡3|≡.|9|4[|*/|↔P|↔c|\]
6454 Express |→α_↓49|4α+↓|4|εi |πin the quater-imaginary
6459 system.|'{A3}|9|1|≡4|≡.|9|4[|*/|↔O|↔C|\] Assume
6462 that we have a |¬m|¬i|¬x program in which location
6471 |¬a contains a number for which the radix point
6480 lies between bytes 3 and 4, while location |¬b
6489 contains a number whose radix point lies between
6497 bytes 2 and 3. (The leftmost byte is number 1).
6507 Where will the radix point be, in registers A
6516 and X, after the instructions|'{A9}|∂!!!!!!!!!!!!!!!!!!!|6|∂
6521 !!!!!!!!!!!!!!!!!!!|6|∂|E|;|>!!|2a)!|¬l|¬d|¬a!|¬a|'
6524 !!|2b)!!|¬l|¬d|¬a!|9|3|¬a|'>|>!!|2|9|6!!|¬m|¬u|¬l!|¬b?|'
6528 !!|2|9|7!!|¬s|¬r|¬a|¬x!|¬5?|'>|>|;!!|2|9|7!!|¬d|¬i|¬v!|¬b|'
6533 >{A9}|9|1|≡5|≡.|9|4[|*/|↔c|↔c|\] Explain why a
6538 negative integer in nines' complement notation
6544 has a representation in ten's complement notation
6551 that is always one greater, if the representations
6559 are regarded as positive.|'|Hβ{U0}{H10L12M29}|π58320#Compute
folio 254 galley 6
6563 r Programming!(Knuth/Addison-Wesley)!f. 254!ch.
6566 4!g. 6|'{A6}{H9L11}|9|1|≡6|≡.|9|4[|*/|↔O|↔o|\]
6569 What are the largest and smallest |εp-|πbit integers
6577 that can be represented in (a) signed-magnitude
6584 binary notation, (b) two's complement notation,
6590 (c) ones' complement notation?|'{A3}|9|1|≡7|≡.|9|4[|εM|π|*/|↔
6594 P|↔c|\] The text de_nes ten's complement notation
6601 only for integers represented in a single computer
6609 word. Is there a way to de_ne a ten's complement
6619 notation |εfor all real numbers, |πhaving ``in_nite
6626 precision,'' analogous to the text's de_nition?
6632 Is there a similar way to de_ne a nines' complement
6642 notation for all real numbers?|'{A3}|9|1|≡8|≡.|9|4[|εM|π|*/|↔
6647 O|↔c|\] Prove Eq. (5).|'{A3}|9|1|≡9|≡.|9|4[|*/|↔O|↔C|\]
6652 Change the following |εoctal |πnumbers to |εhexadecimal
6659 |πnotation, using the hexadecimal digits |¬0,
6665 |¬1,|4.|4.|4.|4, |¬f|¬. |*/|↔O|↔P|≤⊃ |↔C|↔o|↔C|↔C|≤⊃
6669 |↔P|↔C|↔C|↔c|↔P|↔p|↔o|≤⊃ |↔p|↔o|↔C|↔M|↔C|↔L|↔L|↔o|≤⊃
6671 |↔L|↔p|↔P|↔o|↔p|↔C|↔C.|\|'{A3}|≡1|≡0|≡.|9|4[|εM|π|*/|↔P|↔P|\]
6672 Generalize Eq. (5) to mixed radix notation.|'
6680 {A3}|≡1|≡1|≡.|9|4[|*/|↔P|↔P|\] Give an algorithm
6684 which computes the sum of |ε(a|βn|4.|4.|4.|4a|β1a|β0)|βα_↓|β
6689 2 |πand |ε(b|βn|4.|4.|4.|4b|β1b|β0)|βα_↓|β2,
6692 |πusing the |→α_↓2 number system, obtaining the
6699 answer |ε(c|βn|βα+↓|β2|4.|4.|4.|4c|β1c|β0)|βα_↓|β2.|'
6701 {A3}|π|≡1|≡2|≡.|9|4[|*/|↔P|↔L|\] Give algorithms
6704 to convert (a) the binary signed magnitude number
6712 |→|¬N|ε(a|βn|4.|4.|4.|4a|β0)|β2 |πto its negative
6716 binary form |ε(b|βn|βα+↓|β1|4.|4.|4.|4b|β0)|βα_↓|β2;
6719 |πand (b) the negative binary number |ε(b|βn|βα+↓|β1|4.|4.|4
6725 .|4b|β0)|βα_↓|β2 |πto its signed magnitude form
6731 |→|¬N(a|βn|βα+↓|β1|4.|4.|4.|4a|β0)|β2.|'{A3}|≡1|≡3|≡.|9|4[|ε
6732 M|π|*/|↔P|↔O|\] In the decimal system there are
6739 some numbers with two in_nite decimal expansions,
6746 e.g., 2.3599999|4|¬O|4|¬O|4|¬O|4α=↓|42.3600000|4.|4.|4.
6748 Does the |εnegative decimal |π(base |→α_↓10)
6754 system have unique expansions, or are there real
6762 numbers with two di=erent in_nite expansions
6768 in the base also?|'{A3}|≡1|≡4|≡.|9|4[|*/|↔O|↔M|\]
6773 Multiply (11321)|β2|ε|βi |πby itself in the quater-imaginary
6779 system using the method illustrated in the text.|'
6788 {A3}|≡1|≡5|≡.|9|4[|εM|π|*/|↔P|↔M|\] What are the
6792 sets |εS|4α=↓|4|¬T|¬K|βk|β|¬R|β1|4a|βkb|gα_↓|gk|4|¬G|4a|βk
6794 |πan allowable digit|¬Y, analogous to Fig. 1,
6801 for the negative decimal and for the quater-imaginary
6809 number systems?|'{A3}|≡1|≡6|≡.|9|4[|εM|π|*/|↔P|↔M|\]
6812 Design an algorithm to add 1 to |ε(a|βn|4.|4.|4.|4a|β1a|β0)|
6819 βi|βα_↓|β1 |πin the |εi|4α_↓|41 |πnumber system.|'
6825 {A3}|≡1|≡7|≡.|9|4[|εM|π|*/|↔L|↔c|\] It may seem
6829 peculiar that the number |εi|4α_↓|41 |πhas been
6836 given as a number-system base, instead of the
6844 similar but simpler number |εi|4α+↓|41. |πCan
6850 every complex number |εa|4α+↓|4bi, |πwhere |εa
6856 |πand |εb |πare integers, be represented in a
6864 positional number system to base |εi|4α+↓|41,
6870 |πusing only the digits 0 and 1?|'{A3}|≡1|≡8|≡.|9|4[|εHM|π|*/
6877 |↔L|↔P|\] Show that the set |εS |πof Fig. 1 is
6887 a closed set which contains a neighborhood of
6895 the origin. (Consequently, every complex number
6901 has a ``binary'' representation to base |εi|4α_↓|41.)|'
6908 {A3}|π|≡1|≡9|≡.|9|4[|*/|↔P|↔L|\] (David W. Matula.)
6912 Let |εD |πbe a set of |εb |πintegers, containing
6921 exactly one solution to the congruence |εx|4|"o|4j
6928 |π(modulo |εb) |πfor |ε0|4|¬E|4j|4|¬W|4b. |πProve
6933 that all integers |εm |π(positive, negative,
6939 or zero) can be represented in the form |εm|4α=↓|4(a|βn|4.|4
6947 .|4.|4a|β0)|βb, |πwhere all the |εa|βj |πare
6953 in |εD, |πif and only if all integers in the
6963 range |ε|λ3|4|¬E|4m|4|¬E|4u |πcan be represented,
6968 where |ε|λ3|4α=↓|4|→α_↓|πmax|¬T|εa|4|¬G|4a|4|¬A|4D|¬Y/(b|4α_
6969 ↓|41), u|4α=↓|4|→α_↓|πmin|ε|¬Ta|4|¬G|4a|4|¬A|4D|¬Y|¬Y/(b|4α_
6970 ↓|41). |πFor example, |εD|4α=↓|4|¬T|→α_↓1,|40,|4.|4.|4.|4,|4
6973 b|4α_↓|42|¬Y |πsatis_es the conditions for all
6979 |εb|4|¬R|43. [Hint|*/:|\ |πDesign an algorithm
6984 which constructs a suitable representation.]|'
6989 {A3}|≡2|≡0|≡.|9|4[|εHM|π|*/|↔P|↔l|\] (David W.
6992 Matula.) Consider a decimal number system which
6999 uses the digits |εD|4α=↓|4|¬T|→α_↓1, 0, 8, 17,
7006 26, 35, 44, 53, 62, 71|¬Y |πinstead of |¬T|ε0,
7015 1,|4.|4.|4.|4,|49|¬Y. |πThe result of exercise
7020 19 implies (as in exercise 18) that all real
7029 numbers have an in_nite decimal expansion using
7036 digits from |εD.|'|π!|9|7|4In the usual decimal
7043 system, some numbers have two representations
7049 (cf. exercise 13). (a) find a real number which
7058 has |εmore |πthan two |εD-|πdecimal representations.
7064 (b) Show that no real number has in_nitely many
7073 |εD-|πdecimal representations. (c) Show that
7078 uncountably many numbers have two or more |εD-|πdecimal
7086 representations.|'|≡2|≡1|≡.|9|4[|εM|π|*/|↔P|↔P|\]
7088 (C. E. Shannon.) Can every real number (positive,
7096 negative, or zero) be expressed in a ``balanced-decimal''
7104 system, i.e., in the form |ε|¬K|βk|β|¬E|βn|4a|βk10|gk,
7110 |πfor some integer |εn |πand some sequence |εa|βn,
7118 a|βn|βα_↓|β1, a|βn|βα_↓|β2, .|4.|4.|4, |πwhere
7122 each |εa|βk |πis one of the ten numbers |¬T|→α_↓4|f1|d32|),
7131 |→α_↓3|f1|d32|), |→α_↓2|f1|d32|), |→α_↓1|f1|d32|),
7134 |→α_↓|f1|d32|), |f1|d32|), 1|f1|d32|), 2|f1|d32|),
7138 3|f1|d32|), 4|f1|d32|)|¬Y? (Note that zero is
7144 not one of the allowed digits, but we implicitly
7153 assume that |εa|βn|βα+↓|β1, a|βn|βα+↓|β2, .|4.|4.
7158 |πare zero.) Find all representations of zero
7165 in this number system, and _nd all representations
7173 of unity.|'{A3}|≡2|≡2|≡.|9|4[|εHM|π|*/|↔P|↔C|\]
7176 Let |ε|≤a|4α=↓|4|→α_↓|¬K|βm|β|¬R|β1|410|gα_↓|gm|i2.
7178 |πGiven |ε|≤|≤o|4|¬Q|40 |πand any real number
7184 |εx, |πprove that there is a ``decimal'' representation
7192 such that 0|4|¬W|4|¬G|εx|4α_↓|4|¬K|β0|β|¬E|βk|β|¬E|βn|4a|βk1
7194 0|gk|¬G|4|¬W|4|≤o, |πwhere each |εa|βk |πis allowed
7200 to be only one of the three values 0, 1, or |ε|≤a.
7212 |π(Note that no negative powers of 10 are used
7221 in this representation*3)|'{A3}|≡2|≡3|≡.|9|4[|εHM|π|*/|↔L|↔c|\
7224 ] Let |εD |πbe a set of |εb |πreal numbers such
7235 that every positive real number has a representation
7243 |ε|¬K|βk|β|¬E|βn|4a|βk|=∩b|gk |πwith all |εa|βk|4|¬A|4D.
7247 |πExercise 20 shows that there may be many numbers
7256 without |εunique |πrepresentations; but prove
7261 that the set |εT |πof all such numbers has measure
7271 zero.|'{A3}|≡2|≡4|≡.|9|4[|*/|↔L|↔C|\] Find in_nitely
7275 many di=erent sets |εD |πof ten nonnegative integers
7283 satisfying the following three conditions: (i)
7289 gcd(|εD)|4α=↓|41; |π(ii) 0|4|¬A|4|εD; |π(iii)
7293 every positive real number can be represented
7300 in the form |ε|¬K|βk|β|¬E|βn|4a|βk10|gk |πwith
7305 all |εa|βk|4|¬A|4D.|'{A3}|π|≡2|≡5|≡.|9|4[|εM|π|*/|↔P|↔C|\]
7308 (S. A. Cook.) Let |εb, u, |πand |εv |πbe positive
7318 integers, where |εb|4|¬R|4|π2 and 0|4|¬W|4|εv|4|¬W|4b|gm.
7323 |πShow that the base |εb |πrepresentation of
7330 |εu/v |πdoes not contain a run of |εm |πconsecutive
7339 digits equal to |εb|4α_↓|41 |πto the right of
7347 the radix point. (By convention, no runs of in_nitely
7356 many |ε(b|4α_↓|41)|π's are permitted in the standard
7363 base |εb |πrepresentation.)|'{A3}|≡2|≡6|≡.|9|4[|εHM|π|*/|↔L|↔
7366 c|\] (N. S. Mendelsohn.) Let |ε|↔b|≤b|βn|↔v |πbe
7373 a sequence of real numbers de_ned for all integers
7382 |εn, |→α_↓|¬X|4|¬W|4n|4|¬W|4|¬X, |πsuch that|'
7386 {A3}|ε|≤b|βn|4|¬Q|4|≤b|βn|βα+↓|β1;!!|π|uwlim|uc|)|.|εn|¬M|¬X
7386 |)|4|≤b|βn|4α=↓|4|¬X;!!|π|uwlim|uc|)|.|εn|¬M|→α_↓|¬X|)|4|≤b|
7386 βn|4α=↓|40.|;{A9}|πLet |ε|↔bc|βn|↔v |πbe an arbitrary
7392 sequence of positive integers, de_ned for all
7399 integers |εn, |→α_↓|¬X|4|¬W|4n|4|¬W|4|¬X. |πLet
7403 us say that a number |εx |πhas a ``generalized
7412 representation'' if there is an integer |εn |πand
7420 a sequence of integers |εa|βn, a|βn|βα_↓|β1,
7426 a|βn|βα_↓|β2, . . . |πsuch that |εx|4α=↓|4|¬K|βk|β|¬E|βn|4a|
7432 βk|≤b|βk, |πwhere |εa|βn|4|=|↔6α=↓|40, 0|4|¬E|4a|βk|4|¬E|4c|
7435 βk, |πand |εa|βk|4|¬W|4c|βk |πfor in_nitely many
7441 |εk.|'|π!|9|9|2Show that every positive real
7447 number |εx |πhas exactly one generalized representation
7454 if and only if |ε|≤b|βn|βα+↓|β1|4α=↓|4|¬K|βk|β|¬E|βn|4c|βk|≤
7458 b|βk |πfor all |εn. |π(Consequently, the mixed
7465 radix systems with integer bases have this property;
7473 and the mixed radix systems with |ε|≤b|β1|4α=↓|4(c|β0|4α+↓|4
7479 1)|≤b|β0, |≤b|β2|4α=↓|4(c|β1|4α+↓|41)(c|β0|4α+↓|41)|≤b|β0,
7481 . . . , |≤b|βα_↓|β1|4α=↓|4|≤b|β0/(c|βα_↓|β1|4α+↓|41),
7486 . . . |πare the most general number systems of
7496 this type.)|'{A3}|≡2|≡7|≡.|9|4[|εM|π|*/|↔P|↔O|\]
7499 Show that every nonzero integer has a unique
7507 ``reversing binary representation'' |ε2|ge|r0|4α_↓|42|ge|r1|
7510 4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4(|→α_↓1)|gk2|ge|rk
7511 |πwhere |εe|β0|4|¬W|4e|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4e|βk.|'
7513 {A3}|π|≡2|≡8|≡.|9|4[|εM|π|*/|↔P|↔M|\] Show that
7516 every nonzero complex number of the form |εa|4α+↓|4bi
7524 |πwhere |εa |πand |εb |πare integers has a unique
7533 ``revolving binary representation''|'{A9}|ε(1|4α+↓|4i)|ge|r0
7536 |4α+↓|4i(1|4α+↓|4i)|ge|r1|4α_↓|4(1|4α+↓|4i)|ge|r2|4α_↓|4i(1|
7536 4α+↓|4i)|ge|r3|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4i|gk(1|4α+↓|4i)|ge|
7536 rk,|;{A9}|πwhere |εe|β0|4|¬W|4e|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|
7538 4e|βk. |π(Cf. exercise 27.)|'{A3}|≡2|≡9|≡.|9|4[|εM|π|*/|↔L|↔C
7542 |\] (N. G. de Bruijn.) Let |εS|β0, S|β1, S|β2,
7551 . . . |πbe sets of nonnegative integers; we will
7561 say that the collection |εS|β0, S|β1, S|β2, .
7569 . . |πhas Property B if every nonnegative integer
7578 |εn |πcan be written in the form|'{A9}|εn|4α=↓|4s|β0|4α+↓|4s
7585 |β1|4α+↓|4s|β2|4α+↓|4|¬O|4|¬O|4|¬O|4,!!s|βj|4|¬A|4S|βj|;
7586 {A9}|πin exactly one way. (Property B implies
7593 that 0|4|¬A|4|εS|βj |πfor all |εj, |πsince |εn|4α=↓|40
7600 |πcan only be represented as 0|4α+↓|40|4α+↓|40|4α+↓|4|¬O|4|¬
7605 O|4|¬O|4.) Any mixed radix number system with
7612 radices |εb|β0, b|β1, b|β2, . . . |πprovides
7620 an example of sets satisfying Property B, if
7628 we let |εS|βj|4α=↓|4|¬T0,|4q|βj, .|4.|4.|4, (b|βj|4α_↓|41)q|
7632 βj|¬Y, |πwhere |εq|βj|4α=↓|4b|β0b|β1|4.|4.|4.|4b|βj|βα_↓|β1;
7634 |πhere the representation of |εn|4α=↓|4s|β0|4α+↓|4s|β1|4α+↓
7639 |4s|β2|4α+↓|4.|4.|4. |πcorresponds in an obvious
7644 manner to its mixed radix representation (9).
7651 Furthermore, if |εS|β0, S|β1, S|β2, . . . |πhas
7660 Property B, and if |εA|β0, A|β1, A|β2, . . .
7670 |πis any partition of the nonnegative integers
7677 (so that |εA|β0|4|↔q|4A|β1|4|↔q|4A|β2|4|↔q|4|¬O|4|¬O|4|¬O|4α
7679 =↓|4|¬T0, 1, 2, . . .|¬Y |πand |εA|βi|4|↔Q|4A|βj|4α=↓|40
7687 |πfor |εi|4|=|↔6α=↓|4j; |πsome |εA|βj|π's may
7692 be empty), then the ``collapsed'' collection
7698 |εT|β0, T|β1, T|β2, . . . |πalso has Property
7707 B, where |εT|βj |πis the set of all sums |ε|¬K|βi|β|¬A|βA|mj
7716 |4s|βi |πtaken over all possible choices of |εs|βi|4|¬A|4S|β
7723 i.|'|π!|9|9|2Prove that |εany |πcollection |εT|β0,
7729 T|β1, T|β2, . . . |πwhich satis_es Property B
7738 may be obtained by collapsing some collection
7745 |εS|β0, S|β1, S|β2, . . . |πthat corresponds
7753 to a mixed radix number system.|'{A3}|≡3|≡0|≡.|9|4[|εM|π|*/|↔
7759 L|↔m|\] (N. G. de Bruijn.) The radix |→α_↓2 number
7768 system shows us that every integer (positive,
7775 negative, or zero) has a unique representation
7782 of the form|'{A9}(|→α_↓2)|ε|ge|r1|4α+↓|4(|→α_↓2)|ge|r2|4α+↓|
7785 4|¬O|4|¬O|4|¬O|4α+↓|4(|→α_↓2)q|ge|rt,!!e|β1|4|¬Q|4e|β2|4|¬Q|
7785 4|¬O|4|¬O|4|¬O|4|¬Q|4e|βt|4|¬R|40,!!t|4|¬R|40.|;
7786 {A9}|πThe purpose of this exercise is to explore
7794 generalizations of this phenomenon.|'{I1.7H}|9|5a)|9Let
7799 |εb|β0, b|β1, b|β2, . . . |πbe a sequence of
7809 integers such that every integer |εn |πhas a
7817 unique representation of the form|'{A9}!!|2|εn|4α=↓|4b|βe|m1
7822 |4α+↓|4b|βe|m2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4b|βe|mt,!!e|β1|4|¬Q
7822 |4e|β2|4|¬Q|4|¬O|4|¬O|4|¬O|4|¬Q|4e|βt|4|¬R|40,!!t|4|¬R|40.|;
7823 {A9}|π!!|2(Such a sequence |ε|↔bb|βn|↔v |πis
7828 called a ``binary basis.'') Show that there is
7836 an index |εj |πsuch that |εb|βj |πis odd, but
7845 |εb|βk |πis even for all |εk|4|=|↔6α=↓|4j.|'|9|4|πb)|9Prove
7852 that a binary basis |ε|↔bb|βn|↔v |πcan always
7859 be rearranged into the form |εd|β0, 2d|β1, 4d|β2,
7867 . . .|4α=↓|4|↔b2|gnd|βn|↔v, |πwhere each |εd|βk
7873 |πis odd.|'|9|6c)|9If each of |εd|β0, d|β1, d|β2,
7881 . . . |πin (b) is |→|¬N1, prove that |ε|↔bb|βn|↔v
7891 |πis a binary basis if and only if there are
7901 in_nitely many |→α+↓1's and in_nitely many |→α_↓1's.|'
7908 |9|4d)|9Prove that 7, |→α_↓13|4|¬O|42, 7|4|¬O|42|g2,
7913 |→α_↓13|4|¬O|42|g3,|4.|4.|4.|4,|47|4|¬O|42|g2|ε|gk,
7914 |→α_↓13|4|¬O|42|g2|gk|gα+↓|g1,|4.|4.|4. |πis
7916 a binary basis, and _nd the representation of
7924 |εn|4α=↓|41.|'{IC}{A3}|π|≡3|≡1|≡.|9|4[|εM|π|*/|↔L|↔C|\]
7926 A generalization of two's complement arithmetic,
7932 called ``2-adic numbers,'' was invented about
7938 1900 by K. Hensel. (In fact he treated |εp-adic
7947 numbers, |πfor any prime |εp.) |πA 2-adic number
7955 may be regarded as a binary number|'{A9}|εu|4α=↓|4(.|4.|4.|4
7962 u|β3u|β2u|β1u|β0.u|βα_↓|β1|4.|4.|4.|4u|βα_↓|βn)|β2,|;
7963 {A9}|πwhose representation extends in_nitely
7967 far to the left, byt only _nitely many places
7976 to the right, of the binary point. Addition,
7984 subtraction, and multiplication of 2-adic numbers
7990 is done according to the ordinary procedures
7997 of arithmetic, which can in principle be extended
8005 inde_nitely to the left. For example,|'{A9}|9|77|4|∂α=↓|4(.|
8011 4.|4.|4000000000000111)|β2!|7!!!|9|7|f1|d37|)|4|∂α=↓|4(.|4.|
8011 4.|4110110110110111)|β2|9|6|;| |→α_↓7|4|Lα=↓|4(.|4.|4.|41111
8012 11111111001)|β2| |→α_↓|f1|d37|)|4|Lα=↓|4(.|4.|4.|40010010010
8012 01001)|β2>| |f7|d34|)|4|Lα=↓|4(.|4.|4.|4000000000000001.11)|
8013 β2| |f1|d310|)|4|Lα=↓|4(.|4.|4.|4110011001100110.1)|β2>
8014 {H10}|¬H{H9}|v4|→α_↓7|4α=↓|4(.|4.|4.|4100000010110101)|β2
8015 or (.|4.|4.|4011111101001011)|β2.|;|Hβ*?*?*?*?{U0}{H10L12M29}|π5
folio 259 galley 7
8017 8320#Computer Programming!(Knuth/Addison-Wesley)!f.
8019 259!ch. 4!g. 7|'{A6}{H9L11}Here 7 is the ordinary
8027 binary integer seven, while |→α_↓7 is its two's
8035 complement (extending in_nitely to the left);
8041 it is easy to verify that the ordinary procedure
8050 for addition of binary numbers will give |→α_↓7|4α+↓|47|4α=↓
8057 |4(.|4.|4.|400000)|β2|4α=↓|40, when the procedure
8061 is continued inde_nitely. The values of |f1|d37|)
8068 and |→α_↓|f1|d37|) are the unique 2-adic numbers
8075 which, when formally multiplied by 7, give 1
8083 and |→α_↓1, respectively. The values of |f7|d34|)
8090 and |f1|d310|) are examples of 2-adic numbers
8097 which are not 2-adic ``integers,'' since they
8104 have nonzero bits to the right of the binary
8113 point. The two values of {H11}|¬H{H10}|v4|→α_↓7|),
8119 which are negatives of each other, are the two
8128 2-adic numbers which, when formally squared,
8134 yield the value (.|4.|4.|4111111111111001)|β2.|'
8138 {I1.7H}|9|5a)|9Prove that any 2-adic number |εu
8144 |πcan be divided by any nonzero 2-adic number
8152 |εv |πto obtain a unique 2-adic number |εw |πsatisfying
8161 |εu|4α=↓|4vw. |π(Hence the set of 2-adic numbers
8168 forms a ``_eld''; cf. Section 4.6.1.)|'|9|4b)|9Prove
8175 that the 2-adic representation of the rational
8182 number |→α_↓1/(|ε2n|4α+↓|41) |πmay be obtained
8187 as follows, when |εn |πis a positive integer:
8195 First _nd the ordinary binary expansion of 1/(2|εn|4α+↓|41),
8202 |πwhich has the periodic form (0.|ε|≤a|≤a|≤a|4.|4.|4.)|β2
8209 |πfor some string |ε|≤a |πof 0's and 1's. Then
8218 |→α_↓1/|ε(2n|4α+↓|41) |πis the 2-adic number
8223 (.|4.|4.|4|ε|≤a|≤a|≤a)|β2.|'|π|9|6c)|9Prove that
8226 the representation of a 2-adic number |εu |πis
8234 periodic (that is, |βu|βN|βα+↓|β|≤l|4α=↓|4u|βN
8238 |πfor all large |εN, |πfor some |ε|≤l|4|¬R|41)
8245 |πif and only if |εu |πis rational (that is,
8254 |εu|4α=↓|4m/n, |πfor some integers |εm |πand
8260 |εn).|'|π|9|4d)|9Prove that, when |εn |πis an
8267 integer, {H11}|¬H{H10}|v4|εn|) |πis a 2-adic
8272 number if and only if |εn|4|πmod|42|ε|g2|gk|gα+↓|g3|4α=↓|42|
8277 g2|gk |πfor some nonnegative integer |εk. |π(Thus,
8284 either |εn|4|πmod|48|4α=↓|41, or |εn|4|πmod|432|4α=↓|44,
8288 etc.)|'{A3}{IC}|≡3|≡2|≡.|9|4[|εM|π|*/|↔M|↔c|\]
8290 (I. Z. Ruzsa.) Prove that there are in_nitely
8298 many integers whose ternary representation uses
8304 only 0's and 1's and whose quinary representation
8312 uses only 0's, 1's, and 2's.|'{A25}{H10L12}|∨4|∨.|∨2|∨.|9|∨F
8318 |∨L|∨O|∨A|∨T|∨I|∨N|∨G|∨-|∨P|∨O|∨I|∨N|∨T|9|∨A|∨R|∨I|∨T|∨H|∨M|
8318 ∨E|∨T|∨I|∨C|'{A12}|∨4|∨.|∨2|∨.|∨1|∨.|9|∨S|∨i|∨n|∨g|∨l|∨e|∨-|
8319 ∨P|∨r|∨e|∨c|∨i|∨s|∨i|∨o|∨n |∨C|∨a|∨l|∨c|∨u|∨l|∨a|∨t|∨i|∨o|∨n
8320 |∨s|'{A6}In this section, we shall study the
8328 basic principles of doing arithmetic on ``⊗oating-point''
8335 numbers, by analyzing the internal mechanism
8341 of such calculations. Perhaps many readers will
8348 have little interest in this subject, since their
8356 computers either have built-in ⊗oating-point
8361 instructions or therir computer manufacturer
8366 has supplied suitable subroutines. But, in fact,
8373 the material of this section should not merely
8381 be the concern of computer-design engineers or
8388 of a small clique of people who write library
8397 subroutines for new machines; |εevery |πwell-rounded
8403 programmer outht to have a knowledge of what
8411 goes on during the elementary steps of ⊗oating-point
8419 arithmetic. This subject is not at all as trivial
8428 as most people think; it involves a surprising
8436 amount of interesting information.|'{A12}|≡A|≡.|9|≡F|≡l|≡o|≡
8440 a|≡t|≡i|≡n|≡g|≡-|≡p|≡o|≡i|≡n|≡t |≡n|≡o|≡t|≡a|≡t|≡i|≡o|≡n|≡.|
8441 9|4We have discussed ``_xed-point'' notation
8446 for numbers in Section 4.1; in such a case the
8456 programmer knows where the radix point is assumed
8464 to lie in the numbers he manipulates. For many
8473 purposes it is considerably more convenient to
8480 let the position of the radix point be dynamically
8489 variable or ``⊗oating'' as a program is running,
8497 and to carry with each number an indication of
8506 the corresponding radix point position. This
8512 idea has been used for many years in scienti_c
8521 calculations, especially for expressing very
8526 large numbers like Avogadro's number |εN|4α=↓|46.02252|4α⊗↓|
8531 410|g2|g3, or very small numbers like Planck's
8538 constant |εh|4α=↓|41.0545|4α⊗↓|410|gα_↓|g2|g7|4|πerg
8540 sec.|'!|9|7In this section we shall work with
8548 |εbase b, excess q, ⊃oating-point numbers with
8555 p digits|*/: |π|\Such a number is represented
8562 as two quantities |ε(e,|4f), |πand this notation
8569 stands for|'{A9}|ε(e,|4f)|4α=↓|4f|4α⊗↓|4b|ge|gα_↓|gq.|J!(1)|
8571 ;{A9}|πHere |εe |πis an integer having a speci_ed
8580 range, and |εf |πis a signed fraction. We will
8589 adopt the convention that|'{A9}|ε|¬Gf|¬G|4|¬W|41;|;
8594 {A9}|πin other words, the radix point appears
8601 at the left of the positional representation
8608 of |εf. |πMore precisely, the stipulation that
8615 we have |εp-|πdigit numbers means that |εb|gpf
8622 |πis an integer, and that|'{A9}|ε|→α_↓b|gp|4|¬W|4b|gpf|4|¬W|
8627 4b|gp.|J!(2)|;{A9}|πThe term ``⊗oating binary''
8632 implies that |εb|4α=↓|42, |π``⊗oating decimal''
8637 implies |εb|4α=↓|410, |πetc. Using excess 50
8643 ⊗oating-decimal numbers with 8 digits, we can
8650 write, for example,|'{A9}|∂Avogadro's|6number|6|∂|εN|4|∂α=↓|
8653 4(74,|4α+↓.60225200);|;{A4}|L|πPlanck's|6constant|L|εh|Lα=↓|
8654 4(24,|4α+↓.10545000).>{A9}|π!|9|7The two components
8658 |εe |πand |εf |πof a ⊗oating-point number are
8666 called the |εexponent |πand the |εfraction |πparts,
8673 respectively. (Other names are occasionally used
8679 for this purpose, notably ``characteristic''
8684 and ``mantissa''; but it is an abuse of terminology
8693 too call the fraction part a mantissa, since
8701 this concept has quite a di=erent meaning in
8709 connection with logarithms. Furthermore the English
8715 word mantissa means ``a worthless addition.'')|'
8721 {A12}|≡B|≡.|9|≡N|≡o|≡r|≡m|≡a|≡l|≡i|≡z|≡e|≡d |≡c|≡a|≡l|≡c|≡u|
8722 ≡l|≡a|≡t|≡i|≡o|≡n|≡s|≡.|9 A ⊗oating-point number
8726 |ε(e,|4f) |πis said to be |εnormalized |πif the
8734 most signi_cant digit of the representation of
8741 |εf |πis nonzero, so that|'{A9}|ε1/b|4|¬E|4|¬Gf|¬G|4|¬W|41;|
8746 J!(5)|;{A9}|πor if |εf|4α=↓|40 |πand |εe |πhas
8753 its smallest possible value. It is possible to
8761 tell which of two normalized ⊗oating-point numbers
8768 has a greater magnitude by comparing the exponent
8776 parts _rst, and then testing the fraction parts
8784 only if the exponents areq equal.|'|Hβ*?*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
8790